{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e给定一个由整数对组成的序列: $$$(a_1, b_1), (a_2, b_2), \\dots , (a_n, b_n)$$$。如果这个序列按第一个元素的非递减顺序排序,或者按第二个元素的非递减顺序排序,则称之为坏序列。否则,这个序列是好序列。以下是好序列和坏序列的例子:\u003c/p\u003e\n\u003cul\u003e\n \u003cli\u003e$$$s \u003d [(1, 2), (3, 2), (3, 1)]$$$ 是坏序列,因为第一个元素的序列已经排序:$$$[1, 3, 3]$$$;\u003c/li\u003e\n \u003cli\u003e$$$s \u003d [(1, 2), (3, 2), (1, 2)]$$$ 是坏序列,因为第二个元素的序列已经排序:$$$[2, 2, 2]$$$;\u003c/li\u003e\n \u003cli\u003e$$$s \u003d [(1, 1), (2, 2), (3, 3)]$$$ 是坏序列,因为两个序列(第一个元素的序列和第二个元素的序列)都已经排序;\u003c/li\u003e\n \u003cli\u003e$$$s \u003d [(1, 3), (3, 3), (2, 2)]$$$ 是好序列,因为第一个元素的序列 $$$([1, 3, 2])$$$ 和第二个元素的序列 $$$([3, 3, 2])$$$ 都没有排序。\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003e计算大小为 $$$n$$$ 的排列数量,使得将这个排列应用到序列 $$$s$$$ 上后,它变成一个好序列。\u003c/p\u003e\n\u003cp\u003e大小为 $$$n$$$ 的排列 $$$p$$$ 是一个由 $$$n$$$ 个不同整数组成的序列 $$$p_1, p_2, \\dots , p_n$$$,这些整数从 $$$1$$$ 到 $$$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 \u003d [(1, 2), (1, 3), (2, 3)]$$$ 和 $$$p \u003d [2, 3, 1]$$$,那么 $$$s$$$ 就会变成 $$$[(1, 3), (2, 3), (1, 2)]$$$。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e第一行包含一个整数 $$$n$$$($$$1 \\le n \\le 3 \\cdot 10^5$$$)。\u003c/p\u003e\n\u003cp\u003e接下来的 $$$n$$$ 行包含了序列 $$$s$$$ 的描述。第 $$$i$$$ 行包含了序列中第 $$$i$$$ 对整数的第一个和第二个元素 $$$a_i$$$ 和 $$$b_i$$$($$$1 \\le a_i, b_i \\le n$$$)。\u003c/p\u003e\n\u003cp\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003e序列 $$$s$$$ 可能包含相等的元素\u003c/span\u003e。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e打印大小为 $$$n$$$ 的排列数量,使得将这个排列应用到序列 $$$s$$$ 上后,它变成一个好序列。将答案对 $$$998244353$$$(一个质数)取模后输出。\u003c/p\u003e"}},{"title":"示例 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n1 1\n2 2\n3 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"示例 2","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\n2 3\n2 2\n2 1\n2 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"示例 3","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n1 1\n1 1\n2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e在第一个测试用例中,有六种大小为 $$$3$$$ 的排列:\u003c/p\u003e\n\u003col\u003e\n \u003cli\u003e如果 $$$p \u003d [1, 2, 3]$$$,那么 $$$s \u003d [(1, 1), (2, 2), (3, 1)]$$$ — 坏序列(按第一个元素排序);\u003c/li\u003e\n \u003cli\u003e如果 $$$p \u003d [1, 3, 2]$$$,那么 $$$s \u003d [(1, 1), (3, 1), (2, 2)]$$$ — 坏序列(按第二个元素排序);\u003c/li\u003e\n \u003cli\u003e如果 $$$p \u003d [2, 1, 3]$$$,那么 $$$s \u003d [(2, 2), (1, 1), (3, 1)]$$$ — 好序列;\u003c/li\u003e\n \u003cli\u003e如果 $$$p \u003d [2, 3, 1]$$$,那么 $$$s \u003d [(2, 2), (3, 1), (1, 1)]$$$ — 好序列;\u003c/li\u003e\n \u003cli\u003e如果 $$$p \u003d [3, 1, 2]$$$,那么 $$$s \u003d [(3, 1), (1, 1), (2, 2)]$$$ — 坏序列(按第二个元素排序);\u003c/li\u003e\n \u003cli\u003e如果 $$$p \u003d [3, 2, 1]$$$,那么 $$$s \u003d [(3, 1), (2, 2), (1, 1)]$$$ — 好序列。\u003c/li\u003e\n\u003c/ol\u003e"}}]}