题目描述

给定简单无向图 $X$, $Y$, $Z$，它们分别有 $N$ 个顶点和 $M_1$, $M_2$, $M_3$ 条边。$X$, $Y$, $Z$ 中的顶点分别为 $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)$ 为 $W$ 中与选择 $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$ 中一个独立集的最大可能总权重，并将该总权重对 $998,244,353$ 取模后输出。

约束条件

• $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$ 是简单图，即它们没有自环和重边。

输入格式

输入格式如下：

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

输出格式

输出 $W$ 中一个独立集的最大可能总权重，将结果对 $998,244,353$ 取模后输出。

示例输入 1

2
1
1 2
1
1 2
1
1 2

示例输出 1

46494701

独立集的最大可能总权重是 $(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})$ 对 $998,244,353$ 取模后的值，即 $46,494,701$。

示例输入 2

3
3
1 3
1 2
3 2
2
2 1
2 3
1
2 1

示例输出 2

883188316

示例输入 3

100000
1
1 2
1
99999 100000
1
1 100000

示例输出 3

318525248