CF1207D.Number Of Permutations

You are given a sequence of $n$ pairs of integers: $(a_1, b_1), (a_2, b_2), \dots , (a_n, b_n)$. This sequence is called bad if it is sorted in non-descending order by first elements or if it is sorted in non-descending order by second elements. Otherwise the sequence is good. There are examples of good and bad sequences:

• $s = [(1, 2), (3, 2), (3, 1)]$ is bad because the sequence of first elements is sorted: $[1, 3, 3]$;
• $s = [(1, 2), (3, 2), (1, 2)]$ is bad because the sequence of second elements is sorted: $[2, 2, 2]$;
• $s = [(1, 1), (2, 2), (3, 3)]$ is bad because both sequences (the sequence of first elements and the sequence of second elements) are sorted;
• $s = [(1, 3), (3, 3), (2, 2)]$ is good because neither the sequence of first elements $([1, 3, 2])$ nor the sequence of second elements $([3, 3, 2])$ is sorted.

Calculate the number of permutations of size $n$ such that after applying this permutation to the sequence $s$ it turns into a good sequence.

A permutation $p$ of size $n$ is a sequence $p_1, p_2, \dots , p_n$ consisting of $n$ distinct integers from $1$ to $n$ ($1 \le p_i \le n$). If you apply permutation $p_1, p_2, \dots , p_n$ to the sequence $s_1, s_2, \dots , s_n$ you get the sequence $s_{p_1}, s_{p_2}, \dots , s_{p_n}$. For example, if $s = [(1, 2), (1, 3), (2, 3)]$ and $p = [2, 3, 1]$ then $s$ turns into $[(1, 3), (2, 3), (1, 2)]$.

给你一个由 $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)]$ 是坏序列，因为第一个元素序列 $[1, 2, 3]$ 和第二个元素序列 $[1, 2, 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$（即对每个 $i$，均有 $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)]$。

The first line contains one integer $n$ ($1 \le n \le 3 \cdot 10^5$).

The next $n$ lines contains description of sequence $s$. The $i$-th line contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$) — the first and second elements of $i$-th pair in the sequence.

The sequence $s$ may contain equal elements.

第一行包含一个整数 $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$ 中可能包含相等的元素。

Print the number of permutations of size $n$ such that after applying this permutation to the sequence $s$ it turns into a good sequence. Print the answer modulo $998244353$ (a prime number).

输出满足如下条件的大小为 $n$ 的排列的个数：对该排列作用于序列 $s$ 后，所得序列是一个“好序列”。答案对 $998244353$（一个质数）取模。

In first test case there are six permutations of size $3$:

1. if $p = [1, 2, 3]$, then $s = [(1, 1), (2, 2), (3, 1)]$ — bad sequence (sorted by first elements);
2. if $p = [1, 3, 2]$, then $s = [(1, 1), (3, 1), (2, 2)]$ — bad sequence (sorted by second elements);
3. if $p = [2, 1, 3]$, then $s = [(2, 2), (1, 1), (3, 1)]$ — good sequence;
4. if $p = [2, 3, 1]$, then $s = [(2, 2), (3, 1), (1, 1)]$ — good sequence;
5. if $p = [3, 1, 2]$, then $s = [(3, 1), (1, 1), (2, 2)]$ — bad sequence (sorted by second elements);
6. if $p = [3, 2, 1]$, then $s = [(3, 1), (2, 2), (1, 1)]$ — good sequence.

在第一个测试用例中，存在六个长度为 $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)]$ —— 好序列。