ADACROW  Ada and Scarecrow
As you might already know, Ada the Ladybug is a farmer. She has multiple farmhouses and some fields which always connect two adjacent farmhouses. She plans to buy some scarecrows to scare crows!
A scarecrow placed on a farmhouse scares all crows from all adjacent fields. A crow on a field can be disasterous, so Ada has to arrange the scarecrows in such way that they cover all the fields. As scarecrows are pretty expensive she wants to minimize the number of them. Can you count it for her?
Note: Even thought it might look like that from description, the formed "graph" doesn't have to be planar! Also multifields and selffield are not allowed.
Input
The first line contains an integer 1 ≤ T ≤ 100
Each of the next T testcases begins with two integers 1 ≤ N, M ≤ 150, the number of farmhouses and the number of fields.
Each of next M lines contains two numbers 0≤ A_{i},A_{j} < N, the farmhouses, which are connected by a field.
Output
For each testcase output the minimal number of scarecrows Ada has to buy, to cover all fields.
Example Input
6 3 3 1 2 1 0 2 0 4 3 1 2 1 3 1 0 5 6 0 2 0 3 1 3 1 2 1 4 2 4 5 8 0 1 0 3 0 4 1 2 1 4 3 4 3 2 2 4 4 2 0 1 2 3 6 9 0 4 4 3 1 2 2 0 2 3 5 3 4 1 4 2 5 0
Example Output
2 1 3 3 2 3
Example Input 2
2 17 7 12 9 11 8 9 16 11 2 5 14 7 6 8 14 16 23 10 13 11 3 7 14 14 3 9 11 7 8 0 9 8 14 10 8 0 4 6 15 6 12 2 5 10 2 7 11 13 12 15 13 5 3 15 0 6 2 12 9 5 1 1 4
Example Output 2
4 9
hide comments
[Rampage] Blue.Mary:
20170620 05:56:18
[Deleted After AC.] Last edit: 20170620 09:04:03 

Min_25:
20170616 13:15:45
@morass


morass:
20170616 12:28:28
@Min_25: Thank you very much! I updated the testcases (hope I didn't replace any important one :/ ). Now it really TLE's (even though it is a dirty practice :D), 

Min_25:
20170616 12:05:31
@morass:


morass:
20170616 11:47:17
@Min_25: Good day to you. Firstly sorry, but I'm affraid I didn't recognize the pattern of your inputs. So probably not included (I've tried to include some 3/4 regular graphs which shall be [imho] somehow around WC )


Min_25:
20170616 11:03:54
[Edit]


[Rampage] Blue.Mary:
20170616 04:51:16
[Deleted After AC.] Last edit: 20170620 09:04:18 
Added by:  morass 
Date:  20170616 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 