You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[ABC247F] Cards

题面翻译

给定 $n$ 张卡片，每张卡片正反面各有一个数，给定每张卡片正面和反面的数，保证正面的数构成的序列，和反面的数构成的，分别均为 $1$ 到 $n$ 的排列，可以选择任意张卡片并获得其正反面的数，要求最终所有获得的数至少包含 $1$ 到 $n$ 每个数至少一次。求有多少种取法，对 $998244353$ 取模。

题目描述

$1,\ldots,N$ の番号がついた $N$ 枚のカードがあり、カード $i$ の表には $P_i$ が、裏には $Q_i$ が書かれています。
ここで、$P=(P_1,\ldots,P_N)$ 及び $Q=(Q_1,\ldots,Q_N)$ はそれぞれ $(1,\ 2,\ \dots,\ N)$ の並び替えです。

$N$ 枚のカードから何枚かを選ぶ方法のうち、次の条件を満たすものは何通りありますか？ $998244353$ で割った余りを求めてください。

条件：$1,2,\ldots,N$ のどの数も選んだカードのいずれかに書かれている

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $P_1$ $P_2$ $\ldots$ $P_N$ $Q_1$ $Q_2$ $\ldots$ $Q_N$

输出格式

答えを出力せよ。

样例 #1

样例输入 #1

3
1 2 3
2 1 3

样例输出 #1

3

样例 #2

样例输入 #2

5
2 3 5 4 1
4 2 1 3 5

样例输出 #2

12

样例 #3

样例输入 #3

8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8

样例输出 #3

1

提示

制約

• $1\ \leq\ N\ \leq\ 2\times\ 10^5$
• $1\ \leq\ P_i,Q_i\ \leq\ N$
• $P,Q$ はそれぞれ $(1,\ 2,\ \dots,\ N)$ の並び替えである
• 入力に含まれる値は全て整数である

Sample Explanation 1

例えばカード $1,3$ を選ぶと、$1$ はカード $1$ の表に、$2$ はカード $1$ の裏に、$3$ はカード $3$ の表に書かれているため条件を満たします。 条件を満たすカードの選び方は $\{1,3\},\{2,3\},\{1,2,3\}$ の $3$ 通りです。