{"problem":{"name":"Giant Graph","description":{"content":"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","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc043_c"},"statements":[{"statement_type":"Markdown","content":"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})$.\nBased 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$.\nWe will span edges in $W$ as follows:\n\n*   For each edge $(x_u, x_v)$ in $X$ and each $w, l$, span an edge between $(x_u, y_w, z_l)$ and $(x_v, y_w, z_l)$.\n*   For each edge $(y_u, y_v)$ in $Y$ and each $w, l$, span an edge between $(x_w, y_u, z_l)$ and $(x_w, y_v, z_l)$.\n*   For each edge $(z_u, z_v)$ in $Z$ and each $w, l$, span an edge between $(x_w, y_l, z_u)$ and $(x_w, y_l, z_v)$.\n\nThen, 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](https://en.wikipedia.org/wiki/Independent_set_(graph_theory)) in $W$, and print that total weight modulo $998,244,353$.\n\n## Constraints\n\n*   $2 \\leq N \\leq 100,000$\n*   $1 \\leq M_1, M_2, M_3 \\leq 100,000$\n*   $1 \\leq a_i, b_i, c_i, d_i, e_i, f_i \\leq N$\n*   $X$, $Y$, and $Z$ are simple, that is, they have no self-loops and no multiple edges.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$M_1$\n$a_1$ $b_1$\n$a_2$ $b_2$\n$\\vdots$\n$a_{M_1}$ $b_{M_1}$\n$M_2$\n$c_1$ $d_1$\n$c_2$ $d_2$\n$\\vdots$\n$c_{M_2}$ $d_{M_2}$\n$M_3$\n$e_1$ $f_1$\n$e_2$ $f_2$\n$\\vdots$\n$e_{M_3}$ $f_{M_3}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc043_c","tags":[],"sample_group":[["2\n1\n1 2\n1\n1 2\n1\n1 2","46494701\n\nThe 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\n3\n1 3\n1 2\n3 2\n2\n2 1\n2 3\n1\n2 1","883188316"],["100000\n1\n1 2\n1\n99999 100000\n1\n1 100000","318525248"]],"created_at":"2026-03-03 11:01:13"}}