EC_MUN - The world and Contients

no tags 

 

Aplemon is a very active boy and now plans to travel around the world, but before that he
remembered we had five continents , now he thinks it's not true, he wants everyone to live happily
, so he thinks to unite all of the world into one great continent.
Given the description of the countries and their connections with other countries , we say that a
continent is a set of countries that are connected together (being possible to travel to any other
country on the same continent ), forming the continents . Now Aplemon wants to build large
bridges to link these continents , he wants to know what is the minimum number of bridges
needed to connect all the continents and the world is happy. Help him to answer the question.
The first line contains an integer N ( 1 < = N < = 100000 ) the number of countries and M ( 1 < =
M < = 100000 ) that represents the number of connections in the world. Then M lines follow each
containing two integers (x and y) where country x is connected to country y.
Print the minimum amount of bridges Aplemon must build for the world to be happy .
sample input :
5 3
1 2
2 3
4 5
sample output :
1

Aplemon is a very active boy and now plans to travel around the world, but before that he remembered we had five continents , now he thinks it's not true, he wants everyone to live happily, so he thinks to unite all of the world into one great continent.

Given the description of the countries and their connections with other countries , we say that a continent is a set of countries that are connected together (being possible to travel to any other country on the same continent ), forming the continents . Now Aplemon wants to build large bridges to link these continents , he wants to know what is the minimum number of bridges needed to connect all the continents and the world is happy. Help him to answer the question.

Input

The first line contains an integer N ( 1 < = N < = 100000 ) the number of countries and M ( 1 <= M <= 100000 ) that represents the number of connections in the world. 

Output

Print the minimum amount of bridges Aplemon must build for the world to be happy .

Example

Input:

5 3

1 2

2 3

4 5

Output:

1


hide comments
Ehor Nechiporenko: 2014-09-16 08:25:21

Please move this problem to tutorial list, it's trivial. And there are already a lot of problems with the similar conditions in SPOJ

wisfaq: 2014-09-16 08:25:21

Please remove unnecessary language restrictions.


Added by:Eddy Cael
Date:2014-08-31
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C C++ 4.3.2 CPP JAVA
Resource:Internas UTO 2014