Problem Description

This country has $n$ cities and $m$ undirected roads.

A person wants to travel around the country, but they are very picky. They require the travel route to be a BFS (Bread First Search) order: it must visit every city exactly once, and satisfy the following conditions:

• The first city can be chosen arbitrarily.
• Except for the first city, before each city is visited, at least one adjacent city has already been visited.
• The distances from each city to the first city are monotonically non-decreasing. The distance between two cities is defined as the minimum number of edges on a path between them.

This person is also obsessive, and insists on visiting the cities exactly once in the order of labels $1 \sim n$. To make this travel route satisfy all the requirements above, the government needs to build some new roads. What is the minimum number of new roads needed?

Input Format

The first line contains two integers $n, m$.

The next $m$ lines each contain two integers $a, b$, representing an undirected road in this country.

Output Format

Output one line with one integer, representing the required value.

2 0

1

6 3
1 3
2 6
4 5

2

Hint

Explanation for Sample #2

One valid way is to build a road between cities $1$ and $2$, and a road between cities $1$ and $4$. Then the distances from city $1$ to cities $1 \sim 6$ are $0, 1, 1, 1, 2, 2$, respectively.

Constraints

For $\frac{11}{32}$ of the testdata, $1 \leq n \leq 200$.

For $\frac{5}{8}$ of the testdata, $1 \leq n \leq 5 \times 10^3$.

For $100\%$ of the testdata, $1 \leq n \leq 2 \times 10^5$, $0 \leq m \leq \min(2 \times 10^5, \frac{n(n - 1)}{2})$, $1 \leq a, b \leq n$. It is guaranteed that there are no multiple edges or self-loops.

Source

CCO2021 D2T2

Translated by ChatGPT 5