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 < 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]\} $