#1881. [Seerc2008]Lucky cities

题目描述

给出一张N个点M条边的无向简单图，其中N≤100000，M≤100000。定义一个有效的“行程”为一个点数为奇数的简单圈，即所有点在圈上只能出现一次。如果一个点至少处于一个“行程”中，那么它被称为“幸运的”，要求求出图中幸运点的数目。

输入格式

The first line of input contains a single integer T – a number of test cases. Every test case starts with a line containing two integers separated by a single space – N and M. Each of the next M lines will contain two integers ai and bi separated by a single space – the labels of cities that i-th road connects.

输出格式

Output should contain T lines – answers for each of the test cases.

样例

样例输入

1 ≤ T ≤ 77,   

0 ≤ N, M ≤ 100000 (105  

),   

1 ≤ ai < bi ≤ N. 

样例输出

1   

7 7   

1 5   

3 5   

3 7   

1 7   

6 7   

4 7   

4 6 

数据范围与提示

3