CF1207D Number Of Permutations

给定一个长度为 $n$ 的整数对序列：$ (a_1, b_1), (a_2, b_2), \dots , (a_n, b_n) $。如果该序列按第一个元素非递减排序，或者按第二个元素非递减排序，则称该序列为“坏序列”；否则称为“好序列”。下面是一些好序列和坏序列的例子： - $ s = [(1, 2), (3, 2), (3, 1)] $ 是坏序列，因为第一个元素序列 $ [1, 3, 3] $ 已经有序； - $ s = [(1, 2), (3, 2), (1, 2)] $ 是坏序列，因为第二个元素序列 $ [2, 2, 2] $ 已经有序； - $ s = [(1, 1), (2, 2), (3, 3)] $ 是坏序列，因为两个元素序列（第一个元素序列和第二个元素序列）都已经有序； - $ s = [(1, 3), (3, 3), (2, 2)] $ 是好序列，因为无论第一个元素序列 $ ([1, 3, 2]) $ 还是第二个元素序列 $ ([3, 3, 2]) $ 都没有有序。 请计算有多少个长度为 $n$ 的排列，使得将该排列作用于序列 $s$ 后，得到的是一个好序列。 一个长度为 $n$ 的排列 $p$ 是一个由 $1$ 到 $n$ 的 $n$ 个不同整数组成的序列 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$）。如果将排列 $p_1, p_2, \dots, p_n$ 作用于序列 $s_1, s_2, \dots, s_n$，则得到序列 $s_{p_1}, s_{p_2}, \dots, s_{p_n}$。例如，如果 $s = [(1, 2), (1, 3), (2, 3)]$ 且 $p = [2, 3, 1]$，则 $s$ 变为 $[(1, 3), (2, 3), (1, 2)]$。

第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 10^5$）。 接下来的 $n$ 行描述序列 $s$。第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le n$），分别表示第 $i$ 个数对的第一个和第二个元素。 序列 $s$ 可能包含相同的元素对。

输出使得作用排列后序列 $s$ 变为好序列的排列数量。答案对 $998244353$ 取模。

在第一个测试用例中，长度为 $3$ 的排列共有六种： 1. 如果 $p = [1, 2, 3]$，则 $s = [(1, 1), (2, 2), (3, 1)]$ —— 坏序列（按第一个元素有序）； 2. 如果 $p = [1, 3, 2]$，则 $s = [(1, 1), (3, 1), (2, 2)]$ —— 坏序列（按第二个元素有序）； 3. 如果 $p = [2, 1, 3]$，则 $s = [(2, 2), (1, 1), (3, 1)]$ —— 好序列； 4. 如果 $p = [2, 3, 1]$，则 $s = [(2, 2), (3, 1), (1, 1)]$ —— 好序列； 5. 如果 $p = [3, 1, 2]$，则 $s = [(3, 1), (1, 1), (2, 2)]$ —— 坏序列（按第二个元素有序）； 6. 如果 $p = [3, 2, 1]$，则 $s = [(3, 1), (2, 2), (1, 1)]$ —— 好序列。 由 ChatGPT 4.1 翻译