P2207 [USACO13OPEN] Photo B

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.

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 a single integer, the minimum number of photos FJ needs.

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