Photo

Farmer John wants to assemble a panoramic photo of his $N$ cows ($1 \le N \le 200{,}000$), conveniently numbered from $1$ to $N$. He took $M$ photos ($1 \le M \le 100{,}000$); photo $i$ covers the contiguous range of cows from $a_i$ to $b_i$ inclusive ($1 \le a_i \le b_i \le N$). The photos need not cover every cow.

Afterward, Farmer John notices something curious: every photo he took contains exactly one spotted cow. He knows his herd has some spotted cows but has never counted them. Using the photos, determine the maximum possible number of spotted cows the herd could contain. If no way of marking cows as spotted is consistent with all of the photos, output $-1$.

• The first line contains two integers $N$ and $M$.
• Each of the next $M$ lines contains two integers $a_i$ and $b_i$, the range of cows covered by photo $i$.

• Print a single integer: the maximum possible number of spotted cows, or $-1$ if no valid assignment exists.

In the sample there are $5$ cows and $3$ photos, the first covering cows $1$ through $4$. The third photo covers cows $3$ and $4$, so exactly one of them must be spotted; marking either one also satisfies the first two photos, giving a maximum of $1$ spotted cow.