Lucky Cities#1369
John has recently arrived in Romania for the South Eastern European Regional competitions. John has never been to Romania before, so the locals decided to organize a sightseeing tour for him. This tour will include several Romanian cities, and each city will be visited no more than once. John will start in one city, visit other cities according to a guided tour, and finish by returning to the starting city.
There are cities in the country, numbered from to , and two-way roads. Each road connects two different cities. Consider a sightseeing tour for John: c_1, c_2, \ldots, c_n, where each c_i is a city in Romania. All c_i must be distinct. For each i = 1, 2, \ldots, n-1, there must be a road between c_i and c_{i+1}, and there must also be a road between c_n and c_1.
John is an unusual person and wants to visit an odd number of cities. The organizers have planned out all possible tours that visit an odd number of cities. A city is called lucky if there is at least one tour passing through it. Your task is to calculate the number of lucky cities in Romania.
The first line contains a single integer , the number of test cases. Each test case starts with a line containing two integers and separated by a space. Each of the next lines contains two integers a_i and b_i, separated by a space, indicating the labels of the cities connected by the -th road.
Constraints: 1 \le T \le 77, 0 \le N, M \le 100\,000 (10^5), 1 \le a_i < b_i \le N.
Output lines, each containing the answer for the corresponding test case.
Example 1