University of Toronto ACM-ICPC Tryouts 2013
G: Office Mates
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
The input begins with an integer T ≤ 50, the number of test cases. Each test case begins with two integers on their own line: N ≤ 100000, 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
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.
All Submissions
Best Solutions
Point Value: 20
Time Limit: 2.00s
Memory Limit: 64M
Added: Jul 08, 2014
Author: SourSpinach
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)