CF673B.Problems for Round

There are n problems prepared for the next Codeforces round. They are arranged in ascending order by their difficulty, and no two problems have the same difficulty. Moreover, there are m pairs of similar problems. Authors want to split problems between two division according to the following rules:

• Problemset of each division should be non-empty.
• Each problem should be used in exactly one division (yes, it is unusual requirement).
• Each problem used in division 1 should be harder than any problem used in division 2.
• If two problems are similar, they should be used in different divisions.

Your goal is count the number of ways to split problem between two divisions and satisfy all the rules. Two ways to split problems are considered to be different if there is at least one problem that belongs to division 1 in one of them and to division 2 in the other.

Note, that the relation of similarity is not transitive. That is, if problem i is similar to problem j and problem j is similar to problem k, it doesn't follow that i is similar to k.

下一场比赛准备了 $n$ 道题目。这些题目按难度升序排列，且任意两道题的难度均不相同。此外，还有 $m$ 对相似的题目。出题人希望将题目分配给两个分组（Division），并满足以下规则：

• 每个分组的题集都必须非空；
• 每道题目必须且仅能被分配到一个分组中（注意：这是一个不寻常的要求）；
• 所有分配给 Division 1 的题目，其难度必须严格高于所有分配给 Division 2 的题目；
• 若两道题目相似，则它们必须被分配到不同的分组中。

你的目标是计算满足上述所有规则的题目分配方案数。若两种分配方案中至少存在一道题目，在一种方案中属于 Division 1、而在另一种方案中属于 Division 2，则认为这两种方案不同。

注意：相似关系不具备传递性。即，若题目 $i$ 与题目 $j$ 相似，且题目 $j$ 与题目 $k$ 相似，这并不意味着题目 $i$ 与题目 $k$ 相似。

The first line of the input contains two integers n and m (2 ≤ n ≤ 100 000, 0 ≤ m ≤ 100 000) — the number of problems prepared for the round and the number of pairs of similar problems, respectively.

Each of the following m lines contains a pair of similar problems u__i and v__i (1 ≤ u__i, v__i ≤ n, u__i ≠ v__i). It's guaranteed, that no pair of problems meets twice in the input.

输入的第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 100\,000$，$0 \leq m \leq 100\,000$），分别表示为该轮比赛准备的题目数量以及相似题目对的数量。

接下来的 $m$ 行中，每行包含一对相似题目 $u_i$ 和 $v_i$（$1 \leq u_i,\,v_i \leq n$，且 $u_i \neq v_i$）。保证输入中任意一对题目不会重复出现。

Print one integer — the number of ways to split problems in two divisions.

输出一个整数——将题目划分为两个组的方案数。

In the first sample, problems 1 and 2 should be used in division 2, while problems 4 and 5 in division 1. Problem 3 may be used either in division 1 or in division 2.

In the second sample, all pairs of problems are similar and there is no way to split problem between two divisions without breaking any rules.

Third sample reminds you that the similarity relation is not transitive. Problem 3 is similar to both 1 and 2, but 1 is not similar to 2, so they may be used together.

在第一个样例中，题目 1 和 2 应用于第二赛区（Division 2），而题目 4 和 5 应用于第一赛区（Division 1）。题目 3 可以用于第一赛区或第二赛区。

在第二个样例中，所有题目对均彼此相似，因此无法将题目分配到两个赛区而不违反任何规则。

第三个样例提醒你：相似关系不具备传递性。题目 3 与题目 1 和题目 2 均相似，但题目 1 与题目 2 并不相似，因此它们可以共同使用。