CF673B Problems for Round

接下来一场 Codeforces 比赛准备了 $n$ 道题目。这些题目按照难度递增排序，且没有两道题目的难度相同。此外，有 $m$ 对题目是相似的。出题人希望按照如下规则将题目分成两个组： - 每个组必须至少有一道题目； - 每道题目只能被分配到一个组中（是的，这个要求有点不寻常）； - 分给第一组的每道题都要比分给第二组的任意一道题难； - 如果两道题目相似，则它们必须被分配到不同的组。 你的目标是计算有多少种不同的方式将这些题目分到两个组，并满足上述所有规则。如果拆分方式下，至少有一道题目在某个方式中属于第一组，在另一个方式中属于第二组，则认为这两种拆分方式不同。 注意，相似性不是传递性的。也就是说，如果题目 $i$ 与题目 $j$ 相似，题目 $j$ 又与题目 $k$ 相似，并不能推出 $i$ 与 $k$ 也相似。

输入的第一行包含两个整数 $n$ 和 $m$（$2\leq n\leq 100000$，$0\leq m\leq 100000$），分别表示题目数量和相似题目对的数量。 接下来的 $m$ 行，每行包含一对相似的题目 $u_{i}$ 和 $v_{i}$（$1\leq u_{i},v_{i}\leq n,\,u_{i}\neq v_{i}$）。保证输入中没有重复的题目对。

输出一个整数，表示将题目分到两个组的不同合理方式的个数。

在第一个样例中，第 $1$ 题和第 $2$ 题应该分在第 $2$ 组，而第 $4$ 题和第 $5$ 题应该分在第 $1$ 组。第 $3$ 题可以分到任意一组。 在第二个样例中，所有题目对都是相似的，无法满足所有规则，无解。 第三个样例说明相似关系不是传递的。第 $3$ 题分别与第 $1$ 题和第 $2$ 题相似，但第 $1$ 题与第 $2$ 题不相似，因此它们可以分在同一组。 由 ChatGPT 5 翻译