CONGRAPH - Connected country


After a strong earthquake many roads of the ancient country GRAPH were destroyed. The country is divided into disconnected areas so that from one area city it is impossible to reach another area city. Pharaoh wants to restore the road infrastructure and connect all the cities. He asks the great Thoth to find the minimum number of roads needed for this.

Input

The first line of input will contain two space separated integer numbers: 0 < N ≤ 800000, number of cities and 0 < M < 4000000, number of roads. Follow M lines. Each line represents cities (numbering is zero based) connected by road. All roads are bidirectional.

Output

One integer number. Answer of the Thoth

Example

Input:
6 6
0 1
0 2
1 2
3 4
3 5
4 5
Output:
1

Example explanation

One road from the city number 1 to the city number 4 makes GRAPH connected.

 

CONGRAPH



Added by:julkas
Date:2018-05-21
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All