Minseo's Emergency Surgery

Minseo is a newly appointed professor in the Department of Computer Science and Engineering at Kangwon National University. Her research paper on optimal route design for efficient parcel delivery is still widely cited. While teaching enthusiastically today, Minseo could not help but be startled. A student who was dozing off banged their head very hard on the desk. With surgery urgently needed at any moment, Minseo resolved to become a doctor and perform the operation.

The human brain consists of tens of billions of neurons, and each neuron is connected through synapses. Minseo's examination confirmed that the student fell asleep because the connections of some neurons in the brain were severed. If only the severed synapses were restored, the student would wake up, but as you know, Minseo is a computer science professor.

Instead of restoring the severed synapses, Minseo wants to connect all neurons in the brain into a single tree. Here, a tree means a connected graph with no cycles.

Because Minseo is skilled with her hands, she can perform the following operation infinitely many times. She connects two neurons that are not connected, or disconnects two neurons that are already connected.

Given the connection information of the neurons, write a program to find the minimum number of operations needed to connect all neurons into a single tree.

The first line gives the number of neurons N and the number of synapses M.

The following M lines give the numbers u, v of two neurons connected by a synapse.

All input is separated by spaces.

On the first line, print the minimum number of operations needed to connect all neurons into a tree.

• 2 ≤ N ≤ 100,000
• 1 ≤ M ≤ min(N × (N – 1) / 2, 100,000)
• 1 ≤ u, v ≤ N
• u ≠ v
• There is at most one synapse between two neurons.

Since the amount of input is large, using fast input is recommended.