首先能由 \(10^{18(x + y + z)}\) 发现 \(x + y + z\) 肯定越大越好。
于是就能想到贪心,从大到小枚举 \(h = x + y + z\),若 \((x, y, z)\) 没有相连的点被选,那就选这个点。
考虑对于每条边 \((u, v)\),令 \(u < v\),连 \(u\to v\) 的单向边,这样子连出来的图是个 \(\text{DAG}\),因为对于 \((u, a, b), (v, a, b)\),\(v > u, a = a, b = b\),所以绝对不会出现环。
于是就可以考虑 \(\text{DAG}\) 上 \(\text{DP}\),若 \((x, y, z)\) 的后继点已经有一个点选了,那 \((x, y, z)\) 就不选;若 \((x, y, z)\) 的后继点都没选,那 \((x, y, z)\) 就选。
然后能发现选不选的状态和博弈论的必胜必败态很像啊,考虑把这个题目转化为博弈论:
一个棋子在 \((x, y, z)\),每人可以把棋子移动到 \((x, y, z)\) 的后继点上,移动不了就输了。
然后就能发现上面 \(\text{DP}\) 的答案就为这题必败状态的权值。
然后就考虑解这个博弈论,能发现 \(x, y, z\) 其实是相互独立的,所以可以把每一维单独拆出来求。
然后每一维上跑出 \(sg\),答案即为 \(\sum\limits_{sg_{x, i}\oplus sg_{y, j}\oplus sg_{z, k} = 0} 10^{18(i + j + k)}\)。
然后因为 \(\text{DAG}\) 上的 \(sg\) 最大值是 \(O(\sqrt{m})\) 级别的,所以可以枚举 \(sg_{x, i}, sg_{y, j}\) 的值,\(sg_{z,k} = sg_{x, i}\oplus sg_{y, j}\),同时预处理每一维同 \(sg\) 值的 \(10^{18i}\) 的和,直接相乘得到答案。
时间复杂度 \(O(n + m)\)。
// lhzawa(https://www.cnblogs.com/lhzawa/)
// Problem: C - Giant Graph
// Contest: AtCoder - AtCoder Grand Contest 043
// URL: https://atcoder.jp/contests/agc043/tasks/agc043_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const long long mod = 998244353;
const long long base = (long long)(1e18) % mod;
long long pe[N];
int n;
struct SGGraph {
int SG[N], vis[N], ud[N], mxSG;
long long f[N];
basic_string<int> G[N];
void dfs(int u) {
if (ud[u]) {
return ;
}
ud[u] = 1;
for (int v : G[u]) {
dfs(v);
}
for (int v : G[u]) {
vis[SG[v]] = u;
}
for (; vis[SG[u]] == u; SG[u]++);
f[SG[u]] = (f[SG[u]] + pe[u]) % mod, mxSG = max(mxSG, SG[u]);
return ;
}
void init() {
int m;
scanf("%d", &m);
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
G[min(u, v)] += max(u, v);
}
for (int i = 1; i <= n; i++) {
if (! ud[i]) {
dfs(i);
}
}
}
};
SGGraph g[3];
int main() {
scanf("%d", &n);
pe[0] = 1;
for (int i = 1; i <= n; i++) {
pe[i] = pe[i - 1] * base % mod;
}
for (int i = 0; i < 3; i++) {
g[i].init();
}
long long ans = 0;
for (int i = 0; i <= g[0].mxSG; i++) {
for (int j = 0; j <= g[1].mxSG; j++) {
ans = (ans + g[0].f[i] * g[1].f[j] % mod * g[2].f[i ^ j] % mod) % mod;
}
}
printf("%lld\n", ans);
return 0;
}