|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||512 MB||7||6||6||85.714%|
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:
However, someone mistakenly did a bread first search. They found the ordering 1, 2, . . . , 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, . . . , 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?
The first line contains the two integers N and M (1 ≤ N ≤ 200 000, 0 ≤ M ≤ min(200 000, N(N−1)/2)).
The i-th of the next M lines contains the two integers ai and bi (1 ≤ ai, bi ≤ N), representing the two endpoints of the i-th road. It is guaranteed that ai ≠ bi and there is at most one road between any two towns.
On a single line, output the minimum number of roads that must be constructed.
For 1, 2 to be a breadth first search ordering, a road between towns 1 and 2 must be built.
6 3 1 3 2 6 4 5
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.