Description

Farmer John plans to photograph his $n$ cows. They stand in a line and are numbered $1\sim n$ in order.

Each photo can include a contiguous interval of cows in the line. For every cow, FJ wants it to appear in at least one photo.

Unfortunately, there are $k$ pairs of cows that do not get along; they refuse to appear in the same photo. Given the positions of all incompatible pairs, compute the minimum number of photos FJ needs to take.

Input Format

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

Lines $2\sim k+1$: on line $i+1$, there are two integers $a_i$ and $b_i$, indicating that the cow at position $a_i$ and the cow at position $b_i$ are an incompatible pair.

Output Format

Output a single integer, the minimum number of photos FJ needs.

7 3
1 3
2 4
5 6

3

Hint

Sample 1 explanation: FJ can take only three photos: $[1,2],[3,5],[6,7]$.

Constraints: For $100\%$ of the testdata, it is guaranteed that $2\le n\le 10^9$, $1\le k\le 1000$, $1\le a_i, b_i\le n$.

Translated by ChatGPT 5