403152: GYM101047 H Guarding the Temples

There are thousands of Buddhist temples in Thailand, known as "wat". Some of them, such as the "Wat Phra Kaew" in Bangkok's Grand Palace, are specially regarded for their importance and they're called royal temples. The "Wat Phra Kaew" is famous for housing the Emerald Buddha statue, a national treasure. In 2016, the ACM ICPC World Finals will take place in Phuket, Thailand, and so increased tourism is expected in this city. The authorities in Phuket thus want to improve security in its royal temples.

Phuket's Security Unit (PSU) hired the researcher Lua "the ingenious" Kuratowski. PSU needs to solve the following problem. Given N royal temples and M streets connecting them, they must position guards at these streets so that every royal temple can be under surveillance. They consider a temple as secured if there is a guard in at least one of the streets ending at the temple. Streets were laid out so that one can reach any temple from any other. Moreover, due to a cultural dislike of odd numbers, any time someone starts a walk at a temple and returns to it, the number of streets traversed is always even.

Lua knows you wish to advance to the World Finals next year, and she considers this to be a good test for your skills. She challenges you to find a solution with the minimum number of guards.

The first line has a single integer T, the number of test cases.

Each test case spans several input lines. The first line has two integers, N and M, the number of royal temples and the number of streets joining temples, respectively. Each temple is represented by an integer between 1 and N. The next M lines describe the streets. Each street is represented by two integers, corresponding to the temples it joins.

Limits

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 10³
• 1 ≤ M ≤ 5·10³

For each instance, print a single line with the minimum number of guards needed to have all royal temples under surveillance.

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

3
3