Score : 900 points
Given are simple undirected graphs X, Y, Z, with N vertices each and M_1, M_2, M_3 edges, respectively. The vertices in X, Y, Z are respectively called x_1, x_2, \dots, x_N, y_1, y_2, \dots, y_N, z_1, z_2, \dots, z_N. The edges in X, Y, Z are respectively (x_{a_i}, x_{b_i}), (y_{c_i}, y_{d_i}), (z_{e_i}, z_{f_i}).
Based on X, Y, Z, we will build another undirected graph W with N^3 vertices. There are N^3 ways to choose a vertex from each of the graphs X, Y, Z. Each of these choices corresponds to the vertices in W one-to-one. Let (x_i, y_j, z_k) denote the vertex in W corresponding to the choice of x_i, y_j, z_k.
We will span edges in W as follows:
Then, let the weight of the vertex (x_i, y_j, z_k) in W 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 W, and print that total weight modulo 998,244,353.
Input is given from Standard Input in the following format:
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}
Print the maximum possible total weight of an independent set in W, modulo 998,244,353.
2 1 1 2 1 1 2 1 1 2
46494701
The maximum possible total weight of an independent set is that of the set (x_2, y_1, z_1), (x_1, y_2, z_1), (x_1, y_1, z_2), (x_2, y_2, z_2). The output should be (3 \times 10^{72} + 10^{108}) modulo 998,244,353, which is 46,494,701.
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