题目描述

$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$ から $1$ つずつ頂点を選ぶ方法は $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$ の独立集合のうち、頂点の重みの総和の最大値を求めてください。そしてそれを $998,244,353$ で割った余りを出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$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}$

输出格式

重みの総和の最大値を $998,244,353$ で割った余りを出力せよ。

题目大意

给定三个简单无向图$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$。

Translated by Caro23333

2
1
1 2
1
1 2
1
1 2

46494701

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

883188316

100000
1
1 2
1
99999 100000
1
1 100000

318525248

提示

制約

• $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$ は単純、つまり自己ループや多重辺は存在しない

Sample Explanation 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}$ を $998,244,353$ で割ったあまりの $46,494,701$ です。