AT_agc043_c.[AGC043C] Giant Graph

给定 $N$ 个顶点的三个简单无向图 $X$、$Y$、$Z$，它们分别有 $M_1$、$M_2$、$M_3$ 条边。将顶点分别记为 $x_1, x_2, \dots, x_N$，$y_1, y_2, \dots, y_N$，$z_1, z_2, \dots, z_N$。$X$、$Y$、$Z$ 的边分别为 $(x_{a_i}, x_{b_i})$，$(y_{c_i}, y_{d_i})$，$(z_{e_i}, z_{f_i})$。

以 $X$、$Y$、$Z$ 为基础，构造一个有 $N^3$ 个顶点的无向图 $W$。从 $X$、$Y$、$Z$ 各选一个顶点的方法有 $N^3$ 种，每种方法对应 $W$ 的一个顶点。选择 $x_i, y_j, z_k$ 对应的顶点记为 $(x_i, y_j, z_k)$。

$W$ 的边按如下方式添加：

• 对于 $X$ 的每条边 $(x_u, x_v)$，以及所有 $w, l$，在 $(x_u, y_w, z_l)$ 与 $(x_v, y_w, z_l)$ 之间连边。
• 对于 $Y$ 的每条边 $(y_u, y_v)$，以及所有 $w, l$，在 $(x_w, y_u, z_l)$ 与 $(x_w, y_v, z_l)$ 之间连边。
• 对于 $Z$ 的每条边 $(z_u, z_v)$，以及所有 $w, l$，在 $(x_w, y_l, z_u)$ 与 $(x_w, y_l, z_v)$ 之间连边。

$W$ 中顶点 $(x_i, y_j, z_k)$ 的权值为 $1,000,000,000,000,000,000^{(i + j + k)} = 10^{18(i + j + k)}$。请你求出 $W$ 的所有独立集（即任意两点之间没有边相连的集合）中，顶点权值和的最大值，并输出其对 $998244353$ 取模的结果。

输入按以下格式从标准输入读入。

$N$ $M_1$ $a_1$ $b_1$ $a_2$ $b_2$ $\cdots$ $a_{M_1}$ $b_{M_1}$ $M_2$ $c_1$ $d_1$ $c_2$ $d_2$ $\cdots$ $c_{M_2}$ $d_{M_2}$ $M_3$ $e_1$ $f_1$ $e_2$ $f_2$ $\cdots$ $e_{M_3}$ $f_{M_3}$

输出最大权值和对 $998244353$ 取模的结果。

限制条件

• $2 \leq N \leq 100,000$
• $1 \leq M_1, M_2, M_3 \leq 100,000$
• $1 \leq a_i, b_i, c_i, d_i, e_i, f_i \leq N$
• $X$、$Y$、$Z$ 均为简单图，即不存在自环或重边

样例解释 1

选择 $(x_2, y_1, z_1)$、$(x_1, y_2, z_1)$、$(x_1, y_1, z_2)$、$(x_2, y_2, z_2)$ 时最优。答案为 $3 \times 10^{72} + 10^{108}$，对 $998244353$ 取模结果为 $46494701$。

由 ChatGPT 4.1 翻译