Minimum Warehouses

Given an undirected graph representing cities and roads, your task is to determine the minimum number of warehouses required such that every city either hosts a warehouse or is directly adjacent to one. Formally, for each test case you are given two integers \(N\) and \(M\) representing the number of cities and roads respectively, followed by \(M\) pairs of integers. Each pair \((u, v)\) indicates a bidirectional road connecting city \(u\) and city \(v\) (cities are numbered from 1 to \(N\)).

The problem can be interpreted as a coverage problem on graphs. A warehouse placed at a city covers that city and all directly connected neighbors. You are advised to use a greedy strategy: iterate over the cities, and if a city is not yet covered, try to cover it by placing a warehouse on one of its adjacent cities (if possible). The solution should process multiple test cases from the standard input and output the answer for each test case on a separate line.

inputFormat

The first line contains an integer \(T\) representing the number of test cases. The description of each test case is as follows:

• The first line of each test case contains two integers \(N\) and \(M\), representing the number of cities and roads, respectively.
• The next \(M\) lines each contain two integers \(u\) and \(v\), indicating that there is a bidirectional road between city \(u\) and city \(v\).

outputFormat

For each test case, output a single line containing one integer — the minimum number of warehouses needed.

## sample

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

1
2
1
1
2

</p>