E. Nested Segments
combinatorics; dfs and similar; dp; dsu; math
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 < l_j\) or \(r_j < 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\).
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\).
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.
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]\}\)