MSE08D - Lucky cities

no tags 


John has recently arrived in Romania for the South Eastern European Regional competitions. John has never been to Romania before so Romanians decided to organize sightseeing tour for him. This tour will include several Romanian cities and none of them will be visited more than once. John will start in one city and will visit some other cities according to a guide tour. At the end of the tour John will return to the starting point. There are N cities numbered from 1 to N and M two-way roads in the country. Each road connects two different cities. Consider a sightseeing tour for John c1,c2, ...,cn, where each ci denotes a cityin Romania. Then all ci must be distinct, ci and ci+1 must be connected by a road, where i=1,2,...,n-1, cn and c1 must be connected by a road as well.

Being a odd person John would like to visit an odd number of cities. The organizers have drawn the plan of all possible tours with an odd number of cities. Residents of the cities would like John to visit them. So if there is at least one tour passing through some city than this city is called lucky. Your task is to calculate the number of lucky cities in Romania

Input

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

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

 
Constrains:
1 ≤ T ≤ 77,
0 ≤ N, M ≤ 100000 (10^5),
1 ≤ ai < bi ≤ N.



Sample




Input :
1
7 7
1 5
3 5
3 7
1 7
6 7
4 7
4 6
Ouput:
3






hide comments
[Trichromatic] XilinX: 2009-06-19 01:24:08

This problem is moved to tutorial section because an almost the same problem KNIGHTS is available in the classical section.


Added by:psetter
Date:2009-04-09
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Southeastern European 2008