[AGC043C] Giant Graph

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

[problemUrl]: https://atcoder.jp/contests/agc043/tasks/agc043_c $ 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 $ の[独立集合](https://ja.wikipedia.org/wiki/%E7%8B%AC%E7%AB%8B%E9%9B%86%E5%90%88)のうち、頂点の重みの総和の最大値を求めてください。そしてそれを $ 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 $ で割った余りを出力せよ。

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 $ です。