Minimum Checkpoints Conversion

In this problem, you are given multiple test cases. Each test case describes a network of checkpoints connected by trails. Your task is to determine the minimum number of checkpoints that need to be converted into rest areas such that every path a visitor takes from a starting checkpoint to a destination checkpoint passes through exactly one rest area. A visitor's path may even have its starting or ending checkpoint converted into a rest area.

Consider a graph with (n) checkpoints and (m) undirected trails. If (m=0), no path exists so the answer is 1 (i.e. at least one checkpoint should be a rest area). Otherwise, compute the degree of each checkpoint (i.e. the number of trails incident to it). If there are no leaf nodes (i.e. nodes with degree 1), then the optimal answer is 2. Otherwise, the answer is given by (\lfloor \frac{L}{2} \rfloor), where (L) is the number of leaf nodes.

Formally, if (L > 0), then [ \text{result} = \left\lfloor \frac{L}{2} \right\rfloor, \quad \text{else} \quad \text{result} = 2. ]

Note that a checkpoint with no connecting trail (when (m=0)) is considered a trivial case where the answer is 1.

inputFormat

The input is read from standard input (stdin). The first line contains an integer (T) representing the number of test cases. For each test case, the first line contains two integers (n) and (m) where (n) is the number of checkpoints and (m) is the number of trails. Then (m) lines follow, each containing two integers (u) and (v) indicating a trail between checkpoint (u) and checkpoint (v).

outputFormat

For each test case, print the minimum number of checkpoints that need to be converted into rest areas on a separate line, writing the output to standard output (stdout).## sample

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

1
2