[ABC247F] Cards
题意翻译
给定 $ n $ 张卡片，每张卡片正反面各有一个数，给定每张卡片正面和反面的数，保证正面的数构成的序列，和反面的数构成的，分别均为 $ 1 $ 到 $ n $ 的排列，可以选择任意张卡片并获得其正反面的数，要求最终所有获得的数至少包含 $ 1 $ 到 $ n $ 每个数至少一次。求有多少种取法，对 $ 998244353 $ 取模。
题目描述
[problemUrl]: https://atcoder.jp/contests/abc247/tasks/abc247_f
$ 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
3
1 2 3
2 1 3输出样例 #1
3输入样例 #2
5
2 3 5 4 1
4 2 1 3 5输出样例 #2
12输入样例 #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 $ 通りです。