← 返回题目列表

Codeforces · 2056/E

E. 嵌套段

中文机器翻译题面 查看原题

由具有整数端点的成对不同段 $$$[l, r]$$$ 组成的集合 $$$A$$$ 被称为良好,如果 $$$1\le l\le r\le n$$$,并且对于 $$$A$$$ 中的任何一对不同段 $$$[l_i, r_i], [l_j, r_j]$$$,恰好满足以下条件之一:

- $$$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$$$ (一个段完全包含在另一个段内)

给你一个很好的集合 $$$S$$$,由 $$$m$$$ 成对不同的段 $$$[l_i, r_i]$$$ 组成,具有整数端点。您希望向集合 $$$S$$$ 添加尽可能多的附加段,同时确保集合 $$$S$$$ 保持良好状态。

由于此任务太简单,您需要确定向 $$$S$$$ 添加最大数量的附加段的不同方法的数量,确保集合保持良好。如果存在以其中一种方式添加但在另一种中不存在的段,则两种方式被认为是不同的。

形式上,您需要找到不同段的好集合 $$$T$$$ 的数量,使得 $$$S$$$ 是 $$$T$$$ 的子集,并且 $$$T$$$ 具有最大可能的大小。由于结果可能非常大,请以 $$$998\,244\,353$$$ 为模计算答案。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le m \le 2 \cdot 10^5$$$) - 线段的最大右端点,以及 $$$S$$$ 的大小。

接下来的 $$$m$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — 集合 $$$S$$$ 中段的边界。

保证给定的集合 $$$S$$$ 是好的,并且集合 $$$S$$$ 中的段是两两不同的。

保证所有测试用例的 $$$n$$$ 总和和 $$$m$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数,表示不同方式的数量,以 $$$998\,244\,353$$$ 为模,您可以添加最大数量的附加段来设置 $$$S$$$,同时确保设置 $$$S$$$ 保持良好状态。

示例

输入 #1

6
1 0
2 3
1 1
2 2
1 2
5 2
1 3
2 3
4 1
1 1
6 2
1 3
4 6
2300 0

输出 #1

1
1
2
5
4
187997613

注意

在第一个示例中,唯一可能的段是 $$$[1, 1]$$$,因此 $$$T = \{[1, 1]\}$$$ 具有最大大小,并且它是唯一的解决方案。

在第二个示例中,无法添加任何其他段来设置 $$$S$$$。因此,向 $$$S$$$ 添加段的唯一方法就是不添加任何内容。

在第三个示例中,可以向 $$$S$$$ 添加 $$$7$$$ 附加段,同时确保集合保持良好。可以证明,向 $$$S$$$ 添加超过 $$$7$$$ 的附加段是不可能的。将这些$$$7$$$段添加到$$$S$$$中正好有$$$2$$$不同的方法,它们各自的集合$$$T$$$如下所示:

- $$$\{[1, 1], [1, 3], [1, 4], [1, 5], [2, 2], [2, 3], [3, 3], [4, 4], [5, 5]\}$$$
- $$$\{[1, 1], [1, 3], [1, 5], [2, 2], [2, 3], [3, 3], [4, 4], [4, 5], [5, 5]\}$$$.

在第四个例子中,有$$$5$$$不同的方式向$$$S$$$添加最多$$$6$$$个附加段,它们各自的集合$$$T$$$如下所示:

- $$$\{[1, 1], [1, 2], [1, 3], [1, 4], [2, 2], [3, 3], [4, 4]\}$$$
- $$$\{[1, 1], [1, 2], [1, 4], [2, 2], [3, 3], [3, 4], [4, 4]\}$$$
- $$$\{[1, 1], [1, 3], [1, 4], [2, 2], [2, 3], [3, 3], [4, 4]\}$$$
- $$$\{[1, 1], [1, 4], [2, 2], [2, 3], [2, 4], [3, 3], [4, 4]\}$$$
- $$$\{[1, 1], [1, 4], [2, 2], [2, 4], [3, 3], [3, 4], [4, 4]\}$$$