Problem D

Since the underground tunnel between Veröld and Háskólatorg was such a hit the University of Iceland decided to connect all university buildings in a similar manner. Sometimes maintenance needs to be done on the tunnels so it is desirable to be able to get from any building to any other, even with an arbitrary tunnel closed. There are already some tunnels in place and now they need to see how they are doing. Can you determine the minimum number of tunnels to be added such that the above criterion is met?


The first line of the input contains integers $0 \leq n, m \leq 10^5$ where $n$ is the number of buildings and $m$ is the number of tunnels already built. Then follow $m$ lines, each with two integers $1 \leq a, b \leq n$ denoting a tunnel between building $a$ and $b$. The tunnels can be traversed in both directions. The is only one tunnel between each pair of buildings and no building has a tunnel to itself.


One line with a single integer, the minimum number of tunnels to add such that the above criterion is met.

Sample Input 1 Sample Output 1
6 5
1 2
3 2
2 5
4 5
6 5
Sample Input 2 Sample Output 2
3 3
1 2
2 3
3 1

Please log in to submit a solution to this problem

Log in