BFS Tour Road Construction

This country has \(n\) cities and \(m\) bidirectional roads. A traveler wants to tour the country. He is very particular and demands that his tour route satisfies the following conditions:

• The tour is a valid BFS (Breadth First Search) order. He will visit each city exactly once.
• The first city can be chosen arbitrarily (and due to his compulsiveness, the cities must be visited in the order \(1, 2, \dots, n\)).
• For every city except the first, before it is visited at least one of its adjacent cities has already been visited.
• The shortest distances from the first visited city (city 1) to the cities are non-decreasing along the tour order. Here, the distance between two cities is defined as the minimum number of roads on any path connecting them.

Since his desired tour must follow the order \(1, 2, \dots, n\), the government needs to build some new roads so that the final road network makes this touring order a valid BFS order. In other words, for every city \(i\) (where \(2 \le i \le n\)), there must be at least one road connecting it with some city \(j\) with \(j < i\) (so that when city \(i\) is to be visited, a neighbor has been visited earlier) and the final shortest path distances from city 1 satisfy \(d(1) \le d(2) \le \dots \le d(n)\).

Your task is to determine the minimum number of new roads that need to be constructed in order for the desired tour order \(1, 2, \dots, n\) to be a valid BFS order.

Note: If there is already a road connecting a city \(i\) (with \(i \ge 2\)) with some city of lower number, then that city meets the condition. If not, you must add one new road (for example, from city \(i-1\) to city \(i\)).

The input graph is undirected. For each road, if it connects city \(u\) and city \(v\), then consider the pair \((min(u,v), max(u,v))\). For city \(max(u,v))\), having such an edge means one of its neighbors appears earlier in the order. The answer is the count of cities \(i \; (2 \le i \le n)\) that do not have any adjacent city with a smaller number.

Input Format: The first line contains two integers \(n\) and \(m\). Each of the next \(m\) lines contains two integers \(u\) and \(v\), describing a road between city \(u\) and city \(v\).

Output Format: Print a single integer, the minimum number of new roads required.

inputFormat

The first line contains two integers (n) and (m) ((1 \le n \le 10^5), (0 \le m \le 10^5)). Each of the next (m) lines contains two integers (u) and (v) ((1 \le u, v \le n), (u \neq v)), representing a bidirectional road between cities (u) and (v).

outputFormat

Output a single integer: the minimum number of new roads that need to be built so that the traveling order (1, 2, \dots, n) is a valid BFS order starting from city 1.

sample

3 0

2