Farmer John 想為排成一列的 $N$ 頭牛（$(1 \le N \le 200,000)$）拼一張全景照片，牛照常編號 $1..N$。他拍了 $M$ 張照片（$(1 \le M \le 100,000)$），每張涵蓋連續的一段：照片 $i$ 包含牛 $a_i$ 到 $b_i$，含兩端。所有照片未必涵蓋每頭牛。

拍完 FJ 發現每張照片恰好有一頭帶斑點的牛！他知道牛群有些牛帶斑點，但未曾計數。根據照片，求最多可能有幾頭帶斑點的牛。若無法分配斑點使照片結果一致，輸出 $-1$。

輸入格式

• 第 $1$ 行：整數 $N$ 和 $M$。

• 第 $2..M+1$ 行：第 $i+1$ 行含 $a_i$ 和 $b_i$。

輸出格式

• 第 $1$ 行：帶斑點牛的最大可能數量；無解則 $-1$。

範例

輸入格式 1

5 3
1 4
2 5
3 4

輸出格式 1

1

說明

有 $5$ 頭牛、$3$ 張照片。第一張含牛 $1$ 到 $4$，其餘類推。

最後一張表明牛 $3$ 或 $4$ 必須有一頭帶斑點。選任何一頭也滿足前兩張照片。

出題者：Brian Dean，2013