为下一轮 Codeforces 准备了 n 个问题。它们按难度升序排列,没有两个问题具有相同的难度。而且,还有m对类似的问题。作者希望根据以下规则将问题分为两个部分:
- 每个部门的问题集应该是非空的。
- 每个问题都应该在一个部门中使用(是的,这是一个不寻常的要求)。
- 第 1 部分中使用的每个问题都应该比第 2 部分中使用的任何问题更难。
- 如果两个问题相似,则应在不同的部门中使用它们。
您的目标是计算将问题分为两个部分并满足所有规则的方法数量。如果两种划分问题的方法中至少有一个问题在其中一个中属于第 1 部分而在另一个中属于第 2 部分,则认为这两种方法是不同的。
请注意,相似性关系不是传递性的。也就是说,如果问题 i 与问题 j 相似并且问题 j 与问题 k 相似,则并不意味着 i 与 k 相似。
输入
输入的第一行包含两个整数 n 和 m (2 ≤ n ≤ 100 000, 0 ≤ m ≤ 100 000) – 分别为本轮准备的问题数和相似问题对的数量。
以下 m 行中的每一行都包含一对相似的问题 ui 和 vi (1 ≤ ui, vi ≤ n, ui ≠ vi)。可以保证,没有一对问题在输入中出现两次。
输出
打印一个整数——将问题分为两部分的方法数量。
示例
输入 #1
5 2 1 4 5 2
输出 #1
2
输入 #2
3 3 1 2 2 3 1 3
输出 #2
0
输入 #3
3 2 3 1 3 2
输出 #3
1
注意
在第一个示例中,问题 1 和 2 应在分区 2 中使用,而问题 4 和 5 应在分区 1 中使用。问题 3 可以在分区 1 或分区 2 中使用。
在第二个示例中,所有问题对都是相似的,并且无法在不违反任何规则的情况下将问题拆分为两个部分。
第三个示例提醒您相似关系不具有传递性。问题3与1和2相似,但1与2不相似,因此它们可以一起使用。