1770D - Koxia and Game - CodeForces Solution

#include <bits/stdc++.h>
#define INF 1e9
#define INFl 1e18
#define all(x) x.begin(), x.end()
#define sajz(x) (int)x.size()
#define pb push_back
#define s second
#define f first
using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long double ld;
typedef long long ll;

const int N = 1e5+5;
int mod = 998244353;
vi G[N];
bool odw[N];
vi V;

void dfs(int v) {
	V.pb(v);
	odw[v] = true;
	for (auto it : G[v]) if (!odw[it]) dfs(it);
}

void test_case() {
	int n;
	cin >> n;
	vi a(n), b(n);
	for (int i = 1; i <= n; i ++) G[i].clear(), odw[i] = false;
	for (int i = 0; i < n; i ++) cin >> a[i];
	for (int i = 0; i < n; i ++) cin >> b[i];
	ll ans = 1;
	vector<bool> specjalny(n+1);
	for (int i = 0; i < n; i ++) {
		if (a[i] == b[i]) {
			//odw[a[i]] = true;
			specjalny[a[i]] = true;
			ans = (ans * n) % mod;
		}
		else {
			G[a[i]].pb(b[i]);
			G[b[i]].pb(a[i]);
		}
	}
	bool flag = true;
	int ile_spojnych = 0;
	for (int i = 1; i <= n; i ++) {
		if (!odw[i]) {
			V.clear();
			dfs(i);
			int kraw = 0, wierz = 0;
			bool gitara = true;
			for (int j = 0; j < sajz(V); j ++) {
				kraw += sajz(G[V[j]]);
				wierz ++;
				if (specjalny[V[j]]) kraw += 2, gitara = false;
			}
			ile_spojnych += gitara;
			assert(kraw%2==0);
			kraw /= 2;
			debug(kraw, wierz);
			if (kraw != wierz) {
				flag = false;
				break;
			}
		}
	}
	if (!flag) {
		cout << 0 << '\n';
		return;
	}
	for (int i = 0; i < ile_spojnych; i ++) ans = (ans * 2LL) % mod;
	ans %= mod;
	cout << ans << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cout.tie(0);
	cin.tie(0);
	int t=1;
	cin >> t;
	for (int i = 1; i <= t; i ++) {
		test_case();
	}
}