时间限制：1秒　　内存限制：256M

---

题目描述

农夫约翰决定给站在一条线上的 \(N\)（\(1 \le N \le 2 \times 10^5\)）头奶牛制作一张全家福照片，\(N\) 头奶牛编号 \(1\) 到 \(N\)。

于是约翰拍摄了 \(M\)（\(1 \le M \le 1 \times 10^5\)）张照片，每张照片都覆盖了连续一段奶牛：第 \(i\) 张照片中包含了编号 \(a_i\) 到 \(b_i\) 的奶牛。但是这些照片不一定把每一只奶牛都拍了进去。

在拍完照片后，约翰发现了一个有趣的事情：每张照片中都**有且仅有**一只身上带有斑点的奶牛。约翰意识到他的牛群中有一些斑点奶牛，但他从来没有统计过它们的数量。

根据照片，请你帮约翰估算在他的牛群中最多可能有多少只斑点奶牛。如果无解，输出“-1”。

输入格式

第一行包含两个整数 \(N\) 和 \(M\)。

接下来 \(M\) 行，每行包含两个整数 \(a_i\) 和 \(b_i\)。

输出格式

输出斑点牛的最大可能数量。

如果不存在可能解，则输出 \(−1\)。

输入输出样例 #1

输入 #1

5 3 
1 4 
2 5 
3 4 

输出 #1

1 

说明/提示

从最后一张照片可以得出奶牛 \(3\) 或 \(4\) 中，必须有一头斑点牛。

无论哪头是斑点牛，都能使得前两张照片得到满足。