Minimum Doors to Connect Rooms

You are given a number of rooms \(R\) and a number of available doors \(D\). In addition, you are provided with a list of potential door connections between rooms. Your task is to determine the minimum number of doors required to connect all the rooms in such a way that they form a tree structure. Recall that a tree with \(R\) nodes requires exactly \(R-1\) edges (doors) and is acyclic and connected.

If the number of available doors \(D\) is less than \(R-1\), then it is impossible to connect all rooms, and you should output \(-1\). Otherwise, output \(R-1\).

Note: The provided list of door connections does not affect the answer, as the answer is solely based on whether \(D\) is sufficient to form a tree of \(R\) rooms.

inputFormat

The input is given via standard input and consists of multiple lines:

1. The first line contains two integers \(R\) and \(D\) separated by a space, representing the number of rooms and the number of available door connections.
2. The next \(D\) lines each contain two integers \(u\) and \(v\), indicating a door that can connect room \(u\) with room \(v\). If \(D = 0\), no further lines are provided.

outputFormat

Output a single integer which is the minimum number of doors required to connect all the rooms in a tree structure. If it is not possible to connect all the rooms, output \(-1\).

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

3