Canadian Computing Olympiad: 2021 Day 2, Problem 2

There are $N$ towns in a network of $M$ undirected roads. Each road connects one pair of towns. The government has decided to conduct a breadth first search, which means finding an ordering of the $N$ towns such that if the ordering begins with $r$:

• Each town except for $r$ is adjacent to another town given earlier in the order.
• The towns are given in non-decreasing order of distance to $r$. Here, distance means the minimum number of roads that need to be traversed to reach a town.

However, someone mistakenly did a bread first search. They found the ordering $1,2,\dots ,N$ (this was obtained by sorting the towns in increasing order of bread production).

To cover up this embarrassment, the government would like to build new roads such that $1,2,\dots ,N$ is also a possible breadth first search ordering. The new roads can be built between any two towns. What is the minimum possible number of roads that need to be built?

Input Specification

The first line contains the two integers $N$ and $M$ $(1\le N\le 200000,0\le M\le min(200000,\frac{N(N-1)}{2}))$.

The $i$-th of the next $M$ lines contains the two integers $a_i$ and $b_i$ $(1\le a_i,b_i\le N)$, representing the two endpoints of the $i$-th road. It is guaranteed that $a_i\ne b_i$ and there is at most one road between any two towns.

For 5 of the 25 available marks, $N\le 200$.

For an additional 6 of the 25 marks available, $N\le 5000$.

Output Specification

On a single line, output the minimum number of roads that must be constructed.

Sample Input 1

2 0

Sample Output 1

1

Explanation for Sample Output 1

For 1, 2 to be a breadth first search ordering, a road between towns 1 and 2 must be built.

Sample Input 2

6 3
1 3
2 6
4 5

Sample Output 2

2

Explanation for Sample Output 2

By building a road between 1 and 2 and a road between 1 and 4, the sequence of distances becomes $0,1,1,1,2,2$ which is in non-decreasing order.