Good Bye 2022: 2023 is NEAR

D. Koxia and Game

记 \(ans=\prod\limits_{i=1}^{i=n}add_i\)，\(add_i\) 就是 \(i\) 的贡献。
记数字 \(i\) 只和自己连起来称为 \(i\) 自环。

例如：

1 2 3
1 2 3

则称 \(1,2,3\) 自环。

我们先判断 \(ans=0\) 的情况：
(1)

1 2 1
1 3 1

多次出现 \(a_i=b_i=1\)。

(2)

3 3 1
3 3 1

没有出现 \(2\)。

以上两种情况可以肯定 \(ans=0\)。

接下来考虑贡献怎么算：
(1)

1 2 3
1 2 3

显然自环贡献为 \(n\)，此时 \(ans=3\times 3\times 3=27\)。

(2)
看样例：

1 2 2
1 3 3

\(1\) 贡献为 \(3\)，会发现第 \(2\) 和 \(3\) 两个位置直接数字 \(2,3\) 二选一就行了。
\(2,3\) 两个成环，当 \(i=2\) 时，将 \(a_2\) 和 \(b_2\) 双向边连起来，当 \(i=3\) 时，将 \(a_3\) 和 \(b_3\) 双向边连起来，这时数字 \(2\) 和 \(3\) 就是一个环，那么可以知道整个环贡献是 \(2\)。
此时 \(ans=2\times 3=6\)。

(3)

4
1 3 3 4
2 3 4 4

这样 \(ans=0\)，会发现是 \(1\) 和 \(2\) 这条链导致的，我猜测有链就 \(ans=0\)。
那么又发现：

3
1 2 3
1 3 3

这样 \(1\) 自环，\(3\) 自环，\(2\) 是 \(3\) 上的链，但这样 \(ans=9\)，那么我猜测存在孤立链就会导致 \(ans=0\)，此时 \(2\) 的贡献为 \(1\)，就是自环上有链，链的贡献为 \(1\)。

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

constexpr int M = 998244353;

void solve() {
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    a[i]--;
  }
  for (int i = 0; i < n; i++) {
    cin >> b[i];
    b[i]--;
  }
  vector<bool> vis(n);
  for (int i = 0; i < n; i++) {
    if (a[i] == b[i]) {
      if (vis[a[i]]) {
        cout << 0 << '\n';
        return;
      }
      vis[a[i]] = 1;
    }
  }
  vector<vector<int>> g(n);
  for (int i = 0; i < n; i++) {
    g[a[i]].push_back(b[i]);
    g[b[i]].push_back(a[i]);
  }
  for (int i = 0; i < n; i++) {
    if ((int) g[i].size() == 0) {
      cout << 0 << '\n';
      return;
    }
  }
  vis.assign(n, 0);
  i64 ans = 1;
  for (int i = 0; i < n; i++) {
    if (a[i] == b[i]) {
      ans = ans * n % M;
    }
  }
  for (int i = 0; i < n; i++) {
    if (vis[i]) {
      continue;
    }
    int add = 2;
    int cnt1 = 0, cnt2 = 0;
    function<void(int)> dfs = [&](int cur) {
      vis[cur] = 1;
      cnt1++;
      for (auto x : g[cur]) {
        if (cur == x) {
          add = 1;
        }
        cnt2++;
        if (!vis[x]) {
          dfs(x);
        }
      }
    };
    dfs(i);
    if (cnt1 * 2 != cnt2) {
      cout << 0 << '\n';
      return;
    }
    ans = ans * add % M;
  }
  cout << ans << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int tt = 1;
  cin >> tt;
  while (tt--) {
    solve();
  }
  return 0;
}