Fortress Island

You are given a set of N islands and M bidirectional bridges connecting some pairs of islands. Your task is to determine the best island to build a fortress. The best fortress island is defined as the island that minimizes the maximum distance to all other islands. In other words, for each island i, let \(d(i) = \max_{1 \le j \le N} \{dist(i, j)\}\) where \(dist(i,j)\) represents the minimum number of bridges between islands i and j. You need to choose the island i that minimizes \(d(i)\). If there is more than one candidate, choose the one with the smallest identifier.

inputFormat

The first line of the input contains an integer T representing the number of test cases. Each test case is given as follows:

• The first line contains two integers N and M, where N is the number of islands and M is the number of bridges.
• The next M lines each contain two integers u and v indicating there is a bridge between island u and island v.

outputFormat

For each test case, output a single line containing the identifier of the best fortress island.

1
4 4
1 2
2 3
3 4
4 1

1