#agc043c. [agc043_c]Giant Graph

[agc043_c]Giant Graph

Problem Statement

Given are simple undirected graphs XX, YY, ZZ, with NN vertices each and M1M_1, M2M_2, M3M_3 edges, respectively. The vertices in XX, YY, ZZ are respectively called x1,x2,dots,xNx_1, x_2, \\dots, x_N, y1,y2,dots,yNy_1, y_2, \\dots, y_N, z1,z2,dots,zNz_1, z_2, \\dots, z_N. The edges in XX, YY, ZZ are respectively (xai,xbi)(x_{a_i}, x_{b_i}), (yci,ydi)(y_{c_i}, y_{d_i}), (zei,zfi)(z_{e_i}, z_{f_i}).

Based on XX, YY, ZZ, we will build another undirected graph WW with N3N^3 vertices. There are N3N^3 ways to choose a vertex from each of the graphs XX, YY, ZZ. Each of these choices corresponds to the vertices in WW one-to-one. Let (xi,yj,zk)(x_i, y_j, z_k) denote the vertex in WW corresponding to the choice of xi,yj,zkx_i, y_j, z_k.

We will span edges in WW as follows:

  • For each edge (xu,xv)(x_u, x_v) in XX and each w,lw, l, span an edge between (xu,yw,zl)(x_u, y_w, z_l) and (xv,yw,zl)(x_v, y_w, z_l).
  • For each edge (yu,yv)(y_u, y_v) in YY and each w,lw, l, span an edge between (xw,yu,zl)(x_w, y_u, z_l) and (xw,yv,zl)(x_w, y_v, z_l).
  • For each edge (zu,zv)(z_u, z_v) in ZZ and each w,lw, l, span an edge between (xw,yl,zu)(x_w, y_l, z_u) and (xw,yl,zv)(x_w, y_l, z_v).

Then, let the weight of the vertex (xi,yj,zk)(x_i, y_j, z_k) in WW be $1,000,000,000,000,000,000^{(i +j + k)} = 10^{18(i + j + k)}$. Find the maximum possible total weight of the vertices in an independent set in WW, and print that total weight modulo 998,244,353998,244,353.

Constraints

  • 2leqNleq100,0002 \\leq N \\leq 100,000
  • 1leqM1,M2,M3leq100,0001 \\leq M_1, M_2, M_3 \\leq 100,000
  • 1leqai,bi,ci,di,ei,fileqN1 \\leq a_i, b_i, c_i, d_i, e_i, f_i \\leq N
  • XX, YY, and ZZ are simple, that is, they have no self-loops and no multiple edges.

Input

Input is given from Standard Input in the following format:

NN M1M_1 a1a_1 b1b_1 a2a_2 b2b_2 vdots\\vdots aM1a_{M_1} bM1b_{M_1} M2M_2 c1c_1 d1d_1 c2c_2 d2d_2 vdots\\vdots cM2c_{M_2} dM2d_{M_2} M3M_3 e1e_1 f1f_1 e2e_2 f2f_2 vdots\\vdots eM3e_{M_3} fM3f_{M_3}

Output

Print the maximum possible total weight of an independent set in WW, modulo 998,244,353998,244,353.


Sample Input 1

2
1
1 2
1
1 2
1
1 2

Sample Output 1

46494701

The maximum possible total weight of an independent set is that of the set (x2,y1,z1)(x_2, y_1, z_1), (x1,y2,z1)(x_1, y_2, z_1), (x1,y1,z2)(x_1, y_1, z_2), (x2,y2,z2)(x_2, y_2, z_2). The output should be (3times1072+10108)(3 \\times 10^{72} + 10^{108}) modulo 998,244,353998,244,353, which is 46,494,70146,494,701.


Sample Input 2

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

Sample Output 2

883188316

Sample Input 3

100000
1
1 2
1
99999 100000
1
1 100000

Sample Output 3

318525248