ACM U of T Tryouts C3 G - Office Mates

View as PDF

Submit solution

Points: 15
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
University of Toronto ACM-ICPC Tryouts 2013

Dr. Baws has an interesting problem. His N graduate students, while friendly with some select people, are generally not friendly with each other. No graduate student is willing to sit beside a person they aren't friends with.

The desks are up against the wall, in a single line, so it's possible that Dr. Baws will have to leave some desks empty. He does know which students are friends, and fortunately the list is not so long: it turns out that for any subset of K graduate students, there are at most K-1 pairs of friends. Dr. Baws would like you to minimize the total number of desks required. What is this minimum number?

Input Specification

The input begins with an integer T \le 50, the number of test cases. Each test case begins with two integers on their own line: N \le 100\,000, the number of graduate students (who are indexed by the integers 1 through N), and M, the number of friendships among the students. Following this are M lines, each containing two integers i and j separated by a single space. Two integers i and j represent a mutual friendship between students i and j.

The total size of the input file does not exceed 2 MB.

Output Specification

For each test case output a single number: the minimum number of desks Dr. Baws requires to seat the students.

Sample Input

1
6 5
1 2
1 3
1 4
4 5
4 6

Sample Output

7

Explanation of Sample

As seen in the diagram, you seat the students in two groups of three with one empty desk in the middle.


Comments

There are no comments at the moment.