Castle Connectivity and Minimal Roads

In a fictional land, there are \(N\) castles and \(M\) bidirectional roads connecting them. The king wishes that every pair of castles is connected either directly or indirectly, but with the minimal number of roads used. In other words, he wants to build a spanning tree with exactly \(N-1\) roads if possible.

Your task is to determine if it is possible to connect all the castles. If it is possible, output the minimal number of roads required, which is \(N-1\). If it is not possible, output IMPOSSIBLE. Note that if there is only one castle, then no road is needed and the answer is 0.

inputFormat

The first line of input contains an integer \(T\) \( (1 \leq T \leq 10)\), the number of test cases. Each test case begins with a line containing two integers \(N\) and \(M\) (\(1 \leq N \leq 1000\) and \(0 \leq M \leq 10000\)), representing the number of castles and roads respectively. The next \(M\) lines each contain two integers \(u\) and \(v\) (\(1 \leq u,v \leq N\)), indicating a bidirectional road between castle \(u\) and castle \(v\). No pair of castles is connected by more than one road.

outputFormat

For each test case, print a single line. If it is possible to connect all castles, print the minimal number of roads needed (which will be \(N-1\)). Otherwise, print IMPOSSIBLE.

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

3
IMPOSSIBLE