Description
(Domo's friend Kao who gives him the VIP service)
Domo is a brilliant dog, but after this semester, he is very tired and needs to have some rest. Hence, he wants to travel around the world.
Luckily, Domo's friend gives him the VIP service, which can have a flight for free between some cities.
Now, given the number of cities and the free flight list, and Domo starts its travel from the city 0, please find out that how many tickets Domo needs to buy to travel to all the cities (you need 1 ticket to travel from one city to another).
For example, the sample gives 6 cities and 4 pairs of free flights (black line) shown as below:
We need at least two tickets to travel to all the cities (for example, from 1 to 3 and from 3 to 5), hence the answer is 2.
There are two hints for this problem:
Hint 1: (You might get 3/6 with this hint)
If there isn't any cycle on the map, we can directly find the answer using the integer N and K.
In other words, you don't need to consider what the graph looks like, since we can list an equation for the answer with the integer N and K.
Hint 2 : (Complete solution. You may solve this problem with this hint)
visit[] // check whether every city has been visited.
count = 0;
while (!visit_all_cities) {
pick_one_unvisited_city(); // pick an unvisited city.
mark_free_cities(); // mark all the cities we can travel from this city without any ticket.
count++; // increase the group count.
}
ans = ? // find out the relation between the answer and the group count!
Input
The first line consists of two numbers N (1 ≤ N ≤ 100) and K (1 ≤ K ≤ N⋅(N-1)/2) - denoting that there are N cities in the world.
For the next K lines, each line contains two numbers A, B (0 ≤ A, B < N) - denoting that Domo can have a free flight between A and B (A ↔ B).
Output
Print the minimum number of tickets that Domo needs to buy to travel around all the cities.
Remember to print an '\n' at the end of the line.