Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Lucky cities
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 443Accepted: 81

Description

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 city in Romania. Then all ci must be distinct, ci and c(i+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.

Sample Input

1 
7 7 
1 5 
3 5 
3 7 
1 7 
6 7 
4 7 
4 6

Sample Output

3

Hint

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

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator