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