该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在星际探索站β-7的环形生态舱内，驻站科学家为 n 个编号 1~n 的珍稀外星植物样本建立了生长观测系统。

观测系统连续记录了 m 次样本状态，第 i 次记录会覆盖从 si 到 ti 的连续编号的样本。通过分析观测日志，驻站科学家发现了一个关键的规律：每次的样本记录范围内有且仅有 1 株幻光变种菌。

驻站科学家发现原始档案并未记载幻光变种菌的数据情况。请帮助他们根据观测数据，推算该生态舱内最多可能存在多少株幻光变种菌。若无法推算出结果，输出 -1。

输入格式

输入文件名：observe.in
输入第一行，两个空格分隔的整数 n 和 m，分别表示植物样本的数量和观测系统记录的日志数量。
第 2~m+1 行，第 i 行两个空格分隔的整数 si 和 ti，表示第 i 次日志，记录从编号 si 到 ti 的植物样本状态。

输出格式

输出文件名：observe.out
输出一行，一个整数，为该生态舱内最多可能存在的幻光变种菌数量，如果无解输出 -1。

输入样例1

10 5
1 3
2 5
4 9
3 8
4 10

输出样例1

2

数据范围

• 对于 40% 的数据：1 ≤ n ≤ 15，1 ≤ m ≤ 10。
• 对于 100% 的数据：1 ≤ n ≤ 200000，1 ≤ m ≤ 100000。