P15098 [HackerEarth] There is a group of cities known as states. Each state contains a lot of cities but some states are disjoint. Find out minimum number of roads required such that if we pick any two pair
普及-
题目描述

There is a group of cities known as states. Each state contains a lot of cities but some states are disjoint. Find out minimum number of roads required such that if we pick any two pair of cities then path should be there between the two.
Remember that all roads in input may not cover all cities because if there is only one city in a state then there is no possibility of intercity roads

Input
First line contains N,E as input. Next E lines contain two space separated numbers u and v stating there is an edge between u and v

Constraints
1 ≤ N ≤ 10^5
1 ≤ E ≤ 2 x 10^5

SAMPLE INPUT
4 2
1 2
3 4

SAMPLE OUTPUT
1

Explanation

As per the given input for four cities we can guess that there are 2 states and if we add only one road to the map then we can see that every two pair of cities can be reached from one another.

输入格式

见题面

输出格式

见题面

样例输入
100000 100 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 53 53 54 54 55 55 56 56 57 57 58 58 59 59 60 60 61 61 62 62 63 63 64 64 65 65 66 66 67 67 68 68 69 69 70 70 71 71 72 72 73 73 74 74 75 75 76 76 77 77 78 78 79 79 80 80 81 81 82 82 83 83 84 84 85 85 86 86 87 87 88 88 89 89 90 90 91 91 92 92 93 93 94 94 95 95 96 96 97 97 98 98 99 99 100 100 101
样例输出
0