시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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:

• 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, . . . , 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.

## 예제 입력 1

2 0


## 예제 출력 1

1


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

## 예제 입력 2

6 3
1 3
2 6
4 5


## 예제 출력 2

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.