A16574 · Nested Segments

题目描述

如果 $1\le l\le r\le n$ 且 $A$ 中任何一对不同的线段 $[l_i, r_i], [l_j, r_j]$ 都恰好满足以下条件之一，那么由具有整数端点的成对不同线段 $[l, r]$ 组成的集合 $A$ 是好的： - $r_i < l_j$ 或 $r_j < l_i$ （线段不相交） - $l_i \le l_j \le r_j \le r_i$ 或 $l_j \le l_i \le r_i \le r_j$ （一条线段完全包含在另一条线段中） 给你一个由 $m$ 对不同的线段 $[l_i, r_i]$ 组成的好的集合 $S$。您希望在确保集合 $S$ 是好的的前提下，尽可能多地向集合 $S$ 添加线段。 由于这项任务过于简单，因此您需要确定有多少种不同的方法可以在确保集合 $S$ 是好的的情况下，向 $S$ 添加最大数量的额外线段。如果在其中一种方法中增加了一条线段，而在另一种方法中没有增加，那么这两种方法就被认为是不同的。 形式化的，我们需要找出由不同的线段组成的好的的集合 $T$ 的个数，使得 $S$ 是 $T$ 的子集，且 $T$ 的大小最大。由于结果可能很大，请计算答案对 $998\,244\,353$ 取模后的结果。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（ $1 \le t \le 10^4$ ）。测试用例说明如下。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 2 \times 10^5$，$0 \le m \le 2 \times 10^5$）—线段的最大右端点和 $S$ 的大小。 接下来 $m$ 行的 $i$\-th 包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$）—即集合 $S$ 中的线段边界。 保证给定的集合 $S$ 是好的，并且集合 $S$ 中的线段是成对不同的。 保证所有测试用例中 $n$ 和 $m$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出一个整数，表示在确保集合 $S$ 是好的的情况下，在集合 $S$ 中添加最大数量的额外线段的不同方式的数量，模数为 $998\,244\,353$ 。

输入 #1

输出 #1