Place of Guards

In the country of Ajabdesh there are some streets and junc-
tions. Each street connects 2 junctions. The king of Ajabdesh
wants to place some guards in some junctions so that all the
junctions and streets can be guarded by them. A guard in
a junction can guard all the junctions and streets adjacent
to it. But the guards themselves are not gentle. If a street
is guarded by multiple guards then they start ghting. So
the king does not want the scenario where a street may be
guarded by two guards. Given the information about the
streets and junctions of Ajabdesh, help the king to nd the
minimum number of guards needed to guard all the junctions
and streets of his country.
Input
The rst line of the input contains a single integer T (T < 80) indicating the number of test cases.
Each test case begins with 2 integers v (1  v  200) and e (0  e  10000:). v is the number of
junctions and e is the number of streets. Each of the next e line contains 2 integer f and t denoting
that there is a street between f and t. All the junctions are numbered from 0 to v 􀀀 1.
Output
For each test case output in a single line an integer m denoting the minimum number of guards needed
to guard all the junctions and streets. Set the value of m as `-1' if it is impossible to place the guards
without ghting.
Sample Input
2
4 2
0 1
2 3
5 5
0 1
1 2
2 3
0 4
3 4
Sample Output
2
-1