CF2056E.Nested Segments

A set $A$ consisting of pairwise distinct segments $[l, r]$ with integer endpoints is called good if $1\le l\le r\le n$, and for any pair of distinct segments $[l_i, r_i], [l_j, r_j]$ in $A$, exactly one of the following conditions holds:

• $r_i \lt l_j$ or $r_j \lt l_i$ (the segments do not intersect)
• $l_i \le l_j \le r_j \le r_i$ or $l_j \le l_i \le r_i \le r_j$ (one segment is fully contained within the other)

You are given a good set $S$ consisting of $m$ pairwise distinct segments $[l_i, r_i]$ with integer endpoints. You want to add as many additional segments to the set $S$ as possible while ensuring that set $S$ remains good.

Since this task is too easy, you need to determine the number of different ways to add the maximum number of additional segments to $S$, ensuring that the set remains good. Two ways are considered different if there exists a segment that is being added in one of the ways, but not in the other.

Formally, you need to find the number of good sets $T$ of distinct segments, such that $S$ is a subset of $T$ and $T$ has the maximum possible size. Since the result might be very large, compute the answer modulo $998\,244\,353$.

一个由两两互异的整数端点线段 $[l, r]$ 构成的集合 $A$ 被称为好集合，若其满足：$1\le l\le r\le n$，且对 $A$ 中任意两个互异的线段 $[l_i, r_i], [l_j, r_j]$，以下条件中恰好有一个成立：

• $r_i \lt l_j$ 或 $r_j \lt 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$ 的好集合 $S$，其中包含 $m$ 个两两互异的整数端点线段 $[l_i, r_i]$。你希望向集合 $S$ 中添加尽可能多的额外线段，同时保证添加后所得集合仍为好集合。

但本题难度略低，因此你需要计算：在保证集合仍为好集合的前提下，添加最大可能数量的额外线段的不同方案数。若存在某个线段，在一种方案中被添加、而在另一种方案中未被添加，则认为这两种方案不同。

形式化地，你需要计算满足如下条件的好集合 $T$（其元素均为互异线段）的个数：$S \subseteq T$，且 $T$ 具有最大可能的大小。由于答案可能非常大，请将结果对 $998\,244\,353$ 取模。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m \le 2 \cdot 10^5$) — the maximum right endpoint of the segments, and the size of $S$.

The $i$-th of the next $m$ lines contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) — the boundaries of the segments in set $S$.

It is guaranteed that the given set $S$ is good, and the segments in set $S$ are pairwise distinct.

It is guaranteed that both the sum of $n$ and the sum of $m$ over all test cases do not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$ 中第 $i$ 条线段的左右端点。

保证所给集合 $S$ 是“好”的，且集合 $S$ 中的线段两两互不相同。

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

For each test case, output a single integer representing the number of different ways, modulo $998\,244\,353$, that you can add the maximum number of additional segments to set $S$ while ensuring that set $S$ remains good.

对于每个测试用例，输出一个整数，表示在保证集合 $S$ 仍为“好集合”的前提下，向集合 $S$ 中添加最多数量的额外线段的不同方案数，结果对 $998\,244\,353$ 取模。

In the first example, the only possible segment is $[1, 1]$, so $T = {[1, 1]}$ has the maximum size, and it is the only solution.

In the second example, it is not possible to add any additional segments to set $S$. Hence, the only way to add segments to $S$ is adding nothing.

In the third example, it is possible to add $7$ additional segments to $S$ while ensuring that the set remains good. It can be proven that adding more than $7$ additional segments to $S$ is not possible. There are exactly $2$ different ways to add these $7$ segments to $S$, and their respective sets $T$ are shown below:

• ${[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]}$.

In the fourth example, there are exactly $5$ different ways to add a maximum of $6$ additional segments to $S$, and their respective sets $T$ are shown below:

• ${[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]}$

在第一个例子中，唯一可能的线段是 $[1, 1]$，因此 $T = {[1, 1]}$ 具有最大大小，且是唯一的解。

在第二个例子中，无法向集合 $S$ 中添加任何额外的线段。因此，向 $S$ 中添加线段的唯一方式是不添加任何线段。

在第三个例子中，可以在保证集合仍为“好集合”的前提下，向 $S$ 中添加 $7$ 条额外的线段。可以证明：向 $S$ 中添加超过 $7$ 条额外线段是不可能的。恰好存在 $2$ 种不同的方式来向 $S$ 中添加这 $7$ 条线段，它们各自对应的集合 $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]}$