H. Cheating the Group System
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In math class, the teacher is trying a new grouping system. Every day he gives each of his $$$n \cdot 10^{100}$$$ students a card with some number from $$$1$$$ to $$$n$$$, to create $$$n$$$ random groups of equal size $$$10^{100}$$$. This means that he hands out $$$10^{100}$$$ cards with the number $$$1$$$, $$$10^{100}$$$ cards with the number $$$2$$$, ...., and $$$10^{100}$$$ cards with the number $$$n$$$. Each pair of students are either best friends, friends, or not friends. The issue is that students refuse to work in a group without all their best friends (they are okay working without their normal friends), and so they start trading their cards.

The students are socially awkward and only trade their cards with their normal friends and best friends. You are given $$$m$$$ pairs of students, each pair denoting two best friends who must be in the same group (students do not start with any normal friendships). Your job is to compute the minimum number of normal friendships that must be made before the students know their cards such that no matter what cards the students get, after trading any number of times, each pair of best friends has the same cards. Note that if two students are best or normal friends, they can trade infinitely many times.

Input

You will be given $$$n$$$ ($$$2 \leq n \leq 10^9$$$), and $$$m$$$ ($$$1 \leq m \leq 2 \cdot 10^5$$$) in the first line. The next $$$m$$$ lines contain two numbers $$$a$$$ and $$$b$$$ ($$$1 \leq a, b \leq 2 \cdot 10^5$$$), denoting that $$$a$$$ and $$$b$$$ are best friends.

Output

The minimum number of new friendships (not including best friendships).

Example
Input
3 3
1 2
2 3
10 11
Output
3
Note

For the sample case: If we create $$$3 - 4$$$, $$$4 - 5$$$, $$$5 - 10$$$ as new friendships, no matter how the cards are distributed, it can be proved that there exists a sequence of trades such that each of the pairs of best friends will always end up having the same numbered card.

As an example let student $$$1$$$ have card $$$1$$$, student $$$2$$$ have card $$$2$$$, student $$$3$$$ have card $$$3$$$, student $$$4$$$ have card $$$1$$$, student $$$5$$$ have card $$$2$$$, student $$$10$$$ have card $$$3$$$, and student $$$11$$$ have card $$$1$$$ (the rest do not matter).

start - $$$[1, 2, 3, 1, 2, 3, 1]$$$ (each element in the array represents the card of the student in the array $$$[1, 2, 3, 4, 5, 10, 11]$$$)

Here are the trades to satisfy the best friends:

$$$4$$$ swap $$$3$$$ - $$$[1, 2, 1, 3, 2, 3, 1]$$$

$$$3$$$ swap $$$2$$$ - $$$[1, 1, 2, 3, 2, 3, 1]$$$

$$$11$$$ swap $$$10$$$ - $$$[1, 1, 2, 3, 2, 1, 3]$$$

$$$10$$$ swap $$$5$$$ - $$$[1, 1, 2, 3, 1, 2, 3]$$$

$$$5$$$ swap $$$4$$$ - $$$[1, 1, 2, 1, 3, 2, 3]$$$

$$$4$$$ swap $$$3$$$ - $$$[1, 1, 1, 2, 3, 2, 3]$$$

$$$5$$$ swap $$$10$$$ - $$$[1, 1, 1, 2, 2, 3, 3]$$$

Now you can see that all of the best friend's conditions are satisfied.