题意：
给定三个简单无向图\(G_1,G_2,G_3\)，其中每个图的点数均为\(n\)，边数分别为\(m_1,m_2,m_3\)。
现在根据\(G_1,G_2,G_3\)构造一个新的无向图\(G\)。\(G\)有\(n^3\)个点，每个点可以表示为\((x,y,z)\)，对应\(G_1\)中的点\(x\)，\(G_2\)中的点\(y\)，\(G_3\)中的点\(z\)。边集的构造方式如下：
若\(G_1\)中存在一条边\((u,v)\)，则对于任意\(1\le a, b\le n\)，在\(G\)中添加边\(((u,a,b),(v,a,b))\)；
若\(G_2\)中存在一条边\((u,v)\)，则对于任意\(1\le a, b\le n\)，在\(G\)中添加边\(((a,u,b),(a,v,b))\)；
若\(G_3\)中存在一条边\((u,v)\)，则对于任意\(1\le a, b\le n\)，在\(G\)中添加边\(((a,b,u),(a,b,v))\).
对于\(G\)中的任意一个点\((x,y,z)\)，定义其点权为\(10^{18(x+y+z)}\)。
试求\(G\)的最大权独立集的大小模\(998244353\)的值。
\(2\le n\le 10^5, 1\le m_1,m_2,m_3\le 10^5\)。
分析：
由于点权为 \(10^{18(x+y+z)}\)，显然求最大权独立集时可以直接贪心，因为取编号大的一定更优。
考虑只有 \(G_1\) 的情况，我们首先把 \(G_1\) 中的边定向（编号小的连到编号大的），然后可以发现，独立集的定义可以转化成一个经典的博弈问题：给定一张 DAG，两个人轮流操作，最先无法操作的人失败。
因此可以使用 SG 函数解决。对重构图中出度为 \(0\) 的点定义其 \(SG(x)=0\)，然后转移 \(SG(x)=mex(SG(y))\)。
这样做后可以发现 \(SG\) 值为 \(0\) 的点一定会取，因为根据 \(mex\) 的定义，即存在至少一个 \(SG(y)\) 为 \(0\)，那么 \(SG(x)\) 一定不为 \(0\)。这里先手必败就一定会取。
那这里三个图怎么做呢？可以发现每个点的三个维度的值的变换是独立的。
根据 \(SG\) 定理：
对于由 \(n\)个有向图游戏组成的组合游戏，设它们的起点分别为 \(s_1,s_2,...,s_{n}\)，则有定理：当且仅当 \(SG(s_1) \oplus SG(s_2) \oplus ... \oplus SG(s_n) \ne 0\) 时，这个游戏是先手必胜的。
因此我们需要统计：
这东西就很好做了，记 \(f_{i,j}\) 表示目前处理到 \(x_i\)，异或和为 \(j\) 的所有方案的权值和。
转移显然为 f[i + 1][j ^ a[i].SG[g]] += f[i][j] * h[g]。
暴力转移是 \(O(n^2)\) 的。但众所周知，一个 DAG 的 \(SG\) 函数的值域在 \([0,\sqrt m]\)。因此可以做到 \(O(m)\) 或 \(O(n \sqrt m)\) 的时间复杂度，前者需要搞个 \(SG\) 的桶。
代码：
#include<bits/stdc++.h>
#define int long long
#define mod 998244353
#define N 100005
using namespace std;
int read() {
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
void write(int x) {
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar('0' + x % 10);
}
int Pow(int a, int n) {
if(n == 0) return 1;
if(n == 1) return a;
int x = Pow(a, n / 2);
if(n % 2 == 0) return x * x % mod;
else return x * x % mod * a % mod;
}
int n, k, v, h[N];
int z[N], f[7][N]; //f[i][j]表示考虑前i行,异或和为j的权值和
struct Graph{
vector<int>G[N], p[N];
int outd[N], SG[N], t[N]; //t[i]是SG函数的桶
void work(int x) {
for(auto y : p[x]) z[SG[y]] = 1;
SG[x] = 0; while(z[SG[x]]) SG[x]++;
for(auto y : p[x]) z[SG[y]] = 0;
}
void GetSG() { //拓扑排序求SG函数
queue<int>Q;
for(int i = 1; i <= n; i++)
if(outd[i] == 0) Q.push(i);
while(!Q.empty()) {
int x = Q.front();
Q.pop();
for(auto y : G[x]) {
outd[y]--;
if(outd[y] == 0) work(y), Q.push(y);
}
}
for(int i = 1; i <= n; i++) t[SG[i]] += i;
}
}a[7];
signed main() {
n = read();
k = 3;
v = Pow(10, 18) % mod;
h[0] = 1; for(int i = 1; i <= n; i++) h[i] = h[i - 1] * v % mod;
for(int i = 1; i <= k; i++) {
int mi = read();
while(mi--) {
int u = read(), v = read();
if(u > v) swap(u, v); //小的往大的连边
a[i].G[v].push_back(u); //连反向边
a[i].p[u].push_back(v); //连正向边
a[i].outd[u]++;
}
}
for(int i = 1; i <= k; i++) a[i].GetSG();
f[1][0] = 1;
for(int i = 1; i <= k; i++)
for(int j = 0; j <= 700; j++)
for(int g = 1; g <= n; g++) {
f[i + 1][j ^ a[i].SG[g]] += f[i][j] * h[g];
f[i + 1][j ^ a[i].SG[g]] %= mod;
}
write(f[k + 1][0]);
return 0;
}