AKVRRI03 - Joey the President 500 points
Joey is the new president of USA. Not really, just in a movie. As a president he was asked to divide a group of islands into some cities. He thought that if any two islands are connected by a bridge, they should be the part of the same city. For example, if there are six islands, they will be numbered as 1, 2, 3, 4, 5 and 6, and suppose that island 1 is connected to island 2 and island 3 by wo bridges, also island 5 is connected to island 6, then he should divide the islands into 3 cities with islands sets as {1, 2, 3}, {4} and {5, 6}. Given the number of islands and information about the bridges, can you tell him what is the maximum number of cities into which he can divide the islands?
Input
First line will contain two integers "N" the number of islands and "B" the number of bridges. Each of the next "B" lines will contain two integers "A" and "B" which means that island numbered as "A" is connected to island numbered as "B".
Output
Print a single integer denoting the maximum number of cities into which Joey can divide the islands.
Constraints
1 <= N <= 10^5
0 <= B <= Min(10^5, N*(N-1)/2)
Example
Input: 10 8 1 2 1 6 2 6 3 4 8 4 9 10 8 7 4 7 Output: 4
Added by: | Ankit Kumar Vats |
Date: | 2013-08-01 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Self |