Good Bye 2022: 2023 is NEAR

D. Koxia and Game

记 (ans=prodlimits_{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=3times 3times 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=2times 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;
}