### 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)

Butaneon Jun 10, 2015 - 11:31:19 pm UTC ClarificationAlexon Jun 11, 2015 - 3:40:25 am UTC Re: Clarification