Find the Communication Hub

You are given one or more connected graphs, each representing a network of nodes connected by bidirectional roads. Your task is to determine the communication hub for each graph. The communication hub is defined as the node that minimizes the maximum distance to all other nodes in that graph. In other words, let (d(u, v)) be the shortest path length between nodes (u) and (v). For each graph, find the node (h) such that the value (\max_{v}{d(h,v)}) is minimized. If there are several nodes achieving this minimum value, choose the one with the smallest index.

Note: The graph is guaranteed to be connected.

inputFormat

The input begins with an integer (T) (the number of test cases). For each test case, the first line contains two integers (N) and (M), where (N) represents the number of nodes and (M) represents the number of edges. The following (M) lines each contain two integers (u) and (v), indicating that there is a bidirectional road between nodes (u) and (v). It is guaranteed that the graph is connected.

outputFormat

For each test case, output a single line containing the index of the node that serves as the optimal communication hub, i.e., the node which minimizes the maximum distance to all other nodes. If there are multiple candidates, output the smallest index.## sample

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

1
3