Problem:
 Score : 900 points    Problem Statement 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:   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) .  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) .  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) .   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 .      Constraints  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 , and Z are simple, that is, they have no self-loops and no multiple edges.         Input 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}       Output Print the maximum possible total weight of an independent set in W , modulo 998,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 (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 .       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

Solution (Python):
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 998_244_353

@njit((i8, i8[:, :]), cache=True)
def precompute(N, G):
    ng = np.zeros(N + 10, np.bool_)
    g = np.zeros(N + 1, np.int64)
    ind = np.searchsorted(G[:, 0], np.arange(N + 10))
    for v in range(N - 1, 0, -1):
        for i in range(ind[v], ind[v + 1]):
            w = G[i, 1]
            ng[g[w]] = 1
        for n in range(N + 10):
            if ng[n]:
                continue
            break
        g[v] = n
        for i in range(ind[v], ind[v + 1]):
            w = G[i, 1]
            ng[g[w]] = 0

    B = 10**18 % MOD
    power = 1
    A = np.zeros(1024, np.int64)
    for i in range(1, N + 1):
        power = power * B % MOD
        A[g[i]] += power
    return A % MOD

@njit((i8[:], i8[:]), cache=True)
def convolve(A, B):
    C = np.zeros(1024, np.int64)
    for i in range(1024):
        for j in range(1024):
            C[i ^ j] += A[i] * B[j] % MOD
    return C % MOD

N = int(readline())
nums = np.array(read().split(), np.int64)
graphs = []
for _ in range(3):
    M = nums[0]
    G = nums[1:1 + 2 * M].reshape(M, 2)
    G.sort(axis=1)
    G = G[np.argsort(G[:, 0])]
    graphs.append(G)
    nums = nums[1 + 2 * M:]

G1, G2, G3 = map(lambda G: precompute(N, G), graphs)

print(convolve(convolve(G1, G2), G3)[0])

Solution (Python):
import sys
input=sys.stdin.buffer.readline
N,mod=int(input()),998244353
def data():
    edge=[[] for i in range(N)]
    for i in range(int(input())):
        a,b=map(int,input().split())
        if a>b:
            a,b=b,a
        edge[a-1].append(b-1)
    mex=[0]*N
    for i in range(N-1,-1,-1):
        used=[False]*(len(edge[i])+1)
        for pv in edge[i]:
            if mex[pv]<=len(edge[i]):
                used[mex[pv]]=True
        for j in range(len(used)):
            if not used[j]:
                mex[i]=j
                break
    res=[0]*(max(mex)+1)
    for i in range(N):
        res[mex[i]]+=pow(10,18*(i+1),mod)
        res[mex[i]]%=mod
    return res
Data,ans=[data() for i in range(3)],0
for i in range(len(Data[0])):
    for j in range(len(Data[1])):
        if i^j<len(Data[2]):
            ans+=Data[0][i]*Data[1][j]*Data[2][i^j]
            ans%=mod
print(ans)

Solution (Python):
mod=998244353
inv=pow(2,mod-2,mod)

def xorconv(n,X,Y):
    if n==0:
        res=[(X[0]*Y[0])%mod]
        return res
    x=[X[i]+X[i+2**(n-1)] for i in range(2**(n-1))]
    y=[Y[i]+Y[i+2**(n-1)] for i in range(2**(n-1))]
    z=[X[i]-X[i+2**(n-1)] for i in range(2**(n-1))]
    w=[Y[i]-Y[i+2**(n-1)] for i in range(2**(n-1))]
    res1=xorconv(n-1,x,y)
    res2=xorconv(n-1,z,w)
    former=[(res1[i]+res2[i])*inv for i in range(2**(n-1))]
    latter=[(res1[i]-res2[i])*inv for i in range(2**(n-1))]
    former=list(map(lambda x:x%mod,former))
    latter=list(map(lambda x:x%mod,latter))
    return former+latter

import sys

input=sys.stdin.buffer.readline

N=int(input())

def data():
    edge=[[] for i in range(N)]
    for i in range(int(input())):
        a,b=map(int,input().split())
        if a>b:
            a,b=b,a
        edge[a-1].append(b-1)
    mex=[0 for i in range(N)]
    for i in range(N-1,-1,-1):
        used=[False]*(len(edge[i])+1)
        for pv in edge[i]:
            if mex[pv]<=len(edge[i]):
                used[mex[pv]]=True
        for j in range(len(used)):
            if not used[j]:
                mex[i]=j
                break
    res=[0]*(max(mex)+1)
    for i in range(N):
        res[mex[i]]+=pow(10,18*(i+1),mod)
        res[mex[i]]%=mod

    return res

Xdata=data()
Ydata=data()
Zdata=data()

n=0
m=max(len(Xdata),len(Ydata),len(Zdata))
while 2**n<m:
    n+=1

X=[0 for i in range(2**n)]
Y=[0 for i in range(2**n)]
Z=[0 for i in range(2**n)]

for i in range(len(Xdata)):
    X[i]=Xdata[i]

for i in range(len(Ydata)):
    Y[i]=Ydata[i]

for i in range(len(Zdata)):
    Z[i]=Zdata[i]

ans=0
for i in range(2**n):
    for j in range(2**n):
        ans+=X[i]*Y[j]*Z[i^j]
        ans%=mod

print(ans)

Solution (Python):
mod=998244353
inv=pow(2,mod-2,mod)

def xorconv(n,X,Y):
    if n==0:
        res=[(X[0]*Y[0])%mod]
        return res
    x=[X[i]+X[i+2**(n-1)] for i in range(2**(n-1))]
    y=[Y[i]+Y[i+2**(n-1)] for i in range(2**(n-1))]
    z=[X[i]-X[i+2**(n-1)] for i in range(2**(n-1))]
    w=[Y[i]-Y[i+2**(n-1)] for i in range(2**(n-1))]
    res1=xorconv(n-1,x,y)
    res2=xorconv(n-1,z,w)
    former=[(res1[i]+res2[i])*inv for i in range(2**(n-1))]
    latter=[(res1[i]-res2[i])*inv for i in range(2**(n-1))]
    former=list(map(lambda x:x%mod,former))
    latter=list(map(lambda x:x%mod,latter))
    return former+latter

import sys

input=sys.stdin.buffer.readline

N=int(input())

def data():
    edge=[[] for i in range(N)]
    for i in range(int(input())):
        a,b=map(int,input().split())
        if a>b:
            a,b=b,a
        edge[a-1].append(b-1)
    mex=[0 for i in range(N)]
    for i in range(N-1,-1,-1):
        used=[False]*(len(edge[i])+1)
        for pv in edge[i]:
            if mex[pv]<=len(edge[i]):
                used[mex[pv]]=True
        for j in range(len(used)):
            if not used[j]:
                mex[i]=j
                break
    res=[0]*(max(mex)+1)
    for i in range(N):
        res[mex[i]]+=pow(10,18*(i+1),mod)
        res[mex[i]]%=mod

    return res

Xdata=data()
Ydata=data()
Zdata=data()

n=0
m=max(len(Xdata),len(Ydata),len(Zdata))
while 2**n<m:
    n+=1

X=[0 for i in range(2**n)]
Y=[0 for i in range(2**n)]
Z=[0 for i in range(2**n)]

for i in range(len(Xdata)):
    X[i]=Xdata[i]

for i in range(len(Ydata)):
    Y[i]=Ydata[i]

for i in range(len(Zdata)):
    Z[i]=Zdata[i]

YZ=xorconv(n,Y,Z)

ans=0
for i in range(2**n):
    ans+=X[i]*YZ[i]
    ans%=mod

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

mod=998244353

N=int(input())
M1=int(input())
E1=[[] for i in range(N+1)]
for i in range(M1):
    x,y=map(int,input().split())
    E1[x].append(y)
    E1[y].append(x)

M2=int(input())
E2=[[] for i in range(N+1)]
for i in range(M2):
    x,y=map(int,input().split())
    E2[x].append(y)
    E2[y].append(x)

M3=int(input())
E3=[[] for i in range(N+1)]
for i in range(M3):
    x,y=map(int,input().split())
    E3[x].append(y)
    E3[y].append(x)

G1=[-1]*(N+1)
G1[N]=0
for i in range(N-1,-1,-1):
    GS=set()
    for to in E1[i]:
        GS.add(G1[to])
    for j in range(N+1):
        if j in GS:
            continue
        else:
            G1[i]=j
            break

G2=[-1]*(N+1)
G2[N]=0
for i in range(N-1,-1,-1):
    GS=set()
    for to in E2[i]:
        GS.add(G2[to])
    for j in range(N+1):
        if j in GS:
            continue
        else:
            G2[i]=j
            break

G3=[-1]*(N+1)
G3[N]=0
for i in range(N-1,-1,-1):
    GS=set()
    for to in E3[i]:
        GS.add(G3[to])
    for j in range(N+1):
        if j in GS:
            continue
        else:
            G3[i]=j
            break

from collections import Counter
C1=Counter()
C2=Counter()
C3=Counter()

for i in range(1,N+1):
    C1[G1[i]]=(C1[G1[i]]+pow(10,18*i,mod))%mod
    C2[G2[i]]=(C2[G2[i]]+pow(10,18*i,mod))%mod
    C3[G3[i]]=(C3[G3[i]]+pow(10,18*i,mod))%mod
        
C12=Counter()

for c1 in C1:
    for c2 in C2:
        C12[c1^c2]=(C12[c1^c2]+C1[c1]*C2[c2])%mod

ANS=0
for c3 in C3:
    ANS=(ANS+C3[c3]*C12[c3])%mod

print(ANS)

Solution (Python):
import sys
input = sys.stdin.readline

mod=998244353

N=int(input())
M1=int(input())
E1=[[] for i in range(N+1)]
for i in range(M1):
    x,y=map(int,input().split())
    E1[x].append(y)
    E1[y].append(x)

M2=int(input())
E2=[[] for i in range(N+1)]
for i in range(M2):
    x,y=map(int,input().split())
    E2[x].append(y)
    E2[y].append(x)

M3=int(input())
E3=[[] for i in range(N+1)]
for i in range(M3):
    x,y=map(int,input().split())
    E3[x].append(y)
    E3[y].append(x)

G1=[-1]*(N+1)
G1[N]=0
for i in range(N-1,-1,-1):
    GS=set()
    for to in E1[i]:
        GS.add(G1[to])
    for j in range(N+1):
        if j in GS:
            continue
        else:
            G1[i]=j
            break

G2=[-1]*(N+1)
G2[N]=0
for i in range(N-1,-1,-1):
    GS=set()
    for to in E2[i]:
        GS.add(G2[to])
    for j in range(N+1):
        if j in GS:
            continue
        else:
            G2[i]=j
            break

G3=[-1]*(N+1)
G3[N]=0
for i in range(N-1,-1,-1):
    GS=set()
    for to in E3[i]:
        GS.add(G3[to])
    for j in range(N+1):
        if j in GS:
            continue
        else:
            G3[i]=j
            break

from collections import Counter
C1=Counter()
C2=Counter()
C3=Counter()

for i in range(1,N+1):
    C1[G1[i]]=(C1[G1[i]]+pow(10,18*i,mod))%mod
    C2[G2[i]]=(C2[G2[i]]+pow(10,18*i,mod))%mod
    C3[G3[i]]=(C3[G3[i]]+pow(10,18*i,mod))%mod
        
C12=Counter()

for c1 in C1:
    for c2 in C2:
        C12[c1^c2]=(C12[c1^c2]+C1[c1]*C2[c2])%mod

ANS=0
for c3 in C3:
    ANS=(ANS+C3[c3]*C12[c3])%mod

print(ANS)

Solution (Python):
def main():
    """"ここに今までのコード"""
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines

    n = int(readline())
    data = tuple(map(int,read().split()))
    m1 = data[0]
    ab = data[1:1+2*m1]
    m2 = data[1+2*m1]
    cd = data[2+2*m1:2+2*(m1+m2)]
    m3 = data[2+2*(m1+m2)]
    ef = data[3+2*(m1+m2):]

    mod = 998244353
    mods = [1] * (n+10)
    base = pow(10,18,mod)
    for i in range(1,n+1):
        mods[i] = (mods[i-1] * base)%mod

    def calc_node(xy):
        links = [[] for _ in range(n+1)]
        it = iter(xy)
        for x,y in zip(it,it):
            if(x < y):
                x,y = y,x
            links[y].append(x)

        group = [-1] * (n+1)
        g_bit = [0] * (n+1)
        group[-1] = 0
        g_bit[-1] = 1
        num_max = 1
        for i in range(n,0,-1):
            tmp = 0
            for j in links[i]:
                tmp |= g_bit[j]
            cnt = 0
            while(tmp&1):
                tmp = tmp>>1
                cnt+=1
            group[i] = cnt
            g_bit[i] = 1 << cnt
            num_max = max(num_max,cnt)

        res = [0] * (num_max+1)
        for i,num in enumerate(group[1:],1):
            res[num] += mods[i]
            res[num] %= mod

        return res

    x = calc_node(ab)
    y = calc_node(cd)
    z = calc_node(ef)

    if(len(x) < len(y)):
        x,y = y,x
    if(len(y) < len(z)):
        y,z = z,y
    if(len(x) < len(y)):
        x,y = y,x


    len_2 = 2**(len(y)-1).bit_length()
    yz = [0] * (len_2)
    for j in range(len(y)):
        for k in range(len(z)):
            yz[j^k] += y[j]*z[k]
            yz[j^k] %= mod

    ans = 0
    for i,j in zip(x,yz):
        ans += i*j
        ans %= mod

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict

n, *mabs = map(int, sys.stdin.buffer.read().split())
MOD = 998244353
base = 10 ** 18 % MOD
base_costs = [base]
for i in range(n - 1):
    base_costs.append(base_costs[-1] * base % MOD)
graphs = []
i = 0
for _ in range(3):
    m = mabs[i]
    i += 1
    j = i + 2 * m
    parents = [set() for _ in range(n)]
    for a, b in zip(mabs[i:j:2], mabs[i + 1:j:2]):
        a -= 1
        b -= 1
        if a > b:
            a, b = b, a
        parents[a].add(b)
    grundy = [0] * n
    weights = defaultdict(int)
    for v in range(n - 1, -1, -1):
        pgs = {grundy[p] for p in parents[v]}
        for g in range(m + 1):
            if g not in pgs:
                grundy[v] = g
                weights[g] += base_costs[v]
                break

    for g in weights:
        weights[g] %= MOD

    graphs.append(dict(weights))
    i = j

ans = 0
graph_x, graph_y, graph_z = graphs
for gx, cx in graph_x.items():
    for gy, cy in graph_y.items():
        gz = gx ^ gy
        if gz in graph_z:
            ans = (ans + cx * cy * graph_z[gz]) % MOD
print(ans)

Solution (Python):
import itertools
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18

MOD = 998244353




N = int(sys.stdin.buffer.readline())
M = []
m = int(sys.stdin.buffer.readline())
M.append(m)
XVU = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(m)]
m = int(sys.stdin.buffer.readline())
M.append(m)
YVU = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(m)]
m = int(sys.stdin.buffer.readline())
M.append(m)
ZVU = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(m)]

X = [[] for _ in range(N)]
Y = [[] for _ in range(N)]
Z = [[] for _ in range(N)]
for G, VU in zip([X, Y, Z], (XVU, YVU, ZVU)):
    for v, u in VU:
        v -= 1
        u -= 1
        if v > u:
            v, u = u, v
        G[v].append(u)


def grundy(graph):
    ret = [-1] * N
    for v in reversed(range(N)):
        gs = set()
        for u in graph[v]:
            gs.add(ret[u])
        g = 0
        while g in gs:
            g += 1
        ret[v] = g
    return ret


grundy_x = defaultdict(list)
grundy_y = defaultdict(list)
grundy_z = defaultdict(list)
for x, g in enumerate(grundy(X), 1):
    grundy_x[g].append(x)
for y, g in enumerate(grundy(Y), 1):
    grundy_y[g].append(y)
for z, g in enumerate(grundy(Z), 1):
    grundy_z[g].append(z)


base = [1]
for _ in range(N * 3 + 10):
    base.append(base[-1] * pow(10, 18, MOD) % MOD)

ans = 0
for xg, yg in itertools.product(grundy_x.keys(), grundy_y.keys()):
    zg = xg ^ yg
    
    
    xs = 0
    ys = 0
    zs = 0
    for x in grundy_x[xg]:
        xs += base[x]
    for y in grundy_y[yg]:
        ys += base[y]
    for z in grundy_z[zg]:
        zs += base[z]
    ans += xs % MOD * ys % MOD * zs % MOD
    ans %= MOD
print(ans)

Solution (Python):
from collections import defaultdict
import sys

input = lambda: sys.stdin.readline().rstrip()

def mod_inv(a):
  x1, y1, z1 = 1, 0, a
  x2, y2, z2 = 0, 1, M
  while z1 != 1:
    d, m = divmod(z2, z1)
    x1, x2 = x2-d*x1, x1
    y1, y2 = y2-d*y1, y1
    z1, z2 = m, z1
  return x1%M

def mex(s):
  s = set(s)
  for i in range(N+1):
    if i not in s:
      return i

def calc_grundy(e):
  g = {}
  for i in range(N, 0, -1):
    if i not in e:
      continue
    m = mex(map(lambda x:g.get(x, 0), e[i]))
    if m:
      g[i] = m
  return g

def sum_grundy(grundy):
  sum_g = [defaultdict(int, {0:B_sum}) for i in range(3)]
  W, prev = B, 1
  for i in range(1, N+1):
    for s, g in zip(sum_g, grundy):
      if i in g:
        if prev != i:
          W, prev = W * pow(B, i-prev, M) % M, i
        s[g[i]] =  (s[g[i]] + W) % M
        s[0] =  (s[0] - W) % M
  return sum_g

def read_edge():
  M = int(input())
  e = defaultdict(list)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].append(b)
  return e

N = int(input())
M = 998244353
B = pow(10, 18, M)
B_sum = (pow(B, N+1, M) - B) * mod_inv(B-1) % M

edge = [read_edge() for i in range(3)]
grundy = list(map(calc_grundy, edge))
sum_g = sum_grundy(grundy)
ans = 0
for gx, sx in sum_g[0].items():
  for gy, sy in sum_g[1].items():
    gz = gx^gy
    if gz in sum_g[2]:
      ans = (ans + sx*sy*sum_g[2][gz]) % M
print(ans)

Solution (Python):
from collections import defaultdict
import sys

input = lambda: sys.stdin.readline().rstrip()

def mod_inv(a):
  x1, y1, z1 = 1, 0, a
  x2, y2, z2 = 0, 1, M
  while z1 != 1:
    d, m = divmod(z2, z1)
    x1, x2 = x2-d*x1, x1
    y1, y2 = y2-d*y1, y1
    z1, z2 = m, z1
  return x1%M

def mex(s):
  for i in range(N+1):
    if i not in s:
      return i

def calc_grundy(e):
  g = {}
  for i in range(N, 0, -1):
    if i not in e:
      continue
    m = mex({g.get(j, 0) for j in e[i]})
    if m:
      g[i] = m
  return g

def sum_grundy(grundy):
  sum_g = [defaultdict(int, {0:B_sum}) for i in range(3)]
  W, prev = B, 1
  for i in range(1, N+1):
    for s, g in zip(sum_g, grundy):
      if i in g:
        if prev != i:
          W, prev = W * pow(B, i-prev, M) % M, i
        s[g[i]] =  (s[g[i]] + W) % M
        s[0] =  (s[0] - W) % M
  return sum_g

def read_edge():
  M = int(input())
  e = defaultdict(list)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].append(b)
  return e

N = int(input())
M = 998244353
B = pow(10, 18, M)
B_sum = (pow(B, N+1, M) - B) * mod_inv(B-1) % M

edge = [read_edge() for i in range(3)]
grundy = list(map(calc_grundy, edge))
sum_g = sum_grundy(grundy)
ans = 0
for gx, sx in sum_g[0].items():
  for gy, sy in sum_g[1].items():
    gz = gx^gy
    if gz in sum_g[2]:
      ans = (ans + sx*sy*sum_g[2][gz]) % M
print(ans)

Solution (Python):
from collections import defaultdict
import sys

input = lambda: sys.stdin.readline().rstrip()

M = 998244353 

def mod_inv(a, M=M):
  x1, y1, z1 = 1, 0, a
  x2, y2, z2 = 0, 1, M
  while abs(z1) != 1:
    d, m = divmod(z2, z1)
    x1, x2 = x2-d*x1, x1
    y1, y2 = y2-d*y1, y1
    z1, z2 = m, z1
  return x1*z1%M

R_bits = 30
R = 1 << R_bits
R_dec = R - 1
R2 = pow(R, 2, M)
M_neg_inv = mod_inv(-M, R)

def MR(x):
  b = (x * M_neg_inv) & R_dec
  t = x + b * M
  c = t >> R_bits
  d = c - M
  return d if 0 <= d else c

def Montgomery(x):
  return MR(x*R2)

def mex(s):
  for i in range(N+1):
    if i not in s:
      return i

def calc_grundy(edge):
  grundy = [{} for i in range(3)]
  sum_g = [defaultdict(int, {0:M_W_sum}) for i in range(3)]
  M_W = M_W_last
  for i in range(N, 0, -1):
    for g, s, e in zip(grundy, sum_g, edge):
      if i in e:
        m = mex({g.get(j, 0) for j in e[i]})
        if m:
          g[i] = m
          s[g[i]] +=  M_W
          s[0] -=  M_W
    M_W = MR(M_W * M_B_inv)
  return sum_g

def read_edge():
  M = int(input())
  e = defaultdict(list)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].append(b)
  return e

N = int(input())
B = pow(10, 18, M)
M_B_inv = Montgomery(mod_inv(B))
M_W_last = Montgomery(pow(B, N, M))
M_W_sum = MR((M_W_last - Montgomery(1)) * MR(Montgomery(B) * Montgomery(mod_inv(B-1))))

edge = [read_edge() for i in range(3)]
sum_g = calc_grundy(edge)
ans = 0
for gx, sx in sum_g[0].items():
  for gy, sy in sum_g[1].items():
    gz = gx^gy
    sz = sum_g[2][gz]
    if sz:
      ans += MR(MR(sx*sy)*sz)
print(MR(ans)%M)

Solution (Python):
from collections import defaultdict
import sys

input = lambda: sys.stdin.readline().rstrip()

def mod_inv(a):
  x1, y1, z1 = 1, 0, a
  x2, y2, z2 = 0, 1, M
  while z1 != 1:
    d, m = divmod(z2, z1)
    x1, x2 = x2-d*x1, x1
    y1, y2 = y2-d*y1, y1
    z1, z2 = m, z1
  return x1%M

def mex(s):
  for i in range(N+1):
    if i not in s:
      return i

def calc_grundy(edge):
  grundy = [{} for i in range(3)]
  sum_g = [defaultdict(int, {0:W_sum}) for i in range(3)]
  W = W_last
  for i in range(N, 0, -1):
    for g, s, e in zip(grundy, sum_g, edge):
      if i in e:
        m = mex({g.get(j, 0) for j in e[i]})
        if m:
          g[i] = m
          s[g[i]] =  (s[g[i]] + W) % M
          s[0] =  (s[0] - W) % M
    W = W * B_inv % M
  return sum_g

def read_edge():
  M = int(input())
  e = defaultdict(list)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].append(b)
  return e

N = int(input())
M = 998244353
B = pow(10, 18, M)
B_inv = mod_inv(B)
W_last = pow(B, N, M)
W_sum = (W_last - 1) * B * mod_inv(B-1) % M

edge = [read_edge() for i in range(3)]
sum_g = calc_grundy(edge)
ans = 0
for gx, sx in sum_g[0].items():
  for gy, sy in sum_g[1].items():
    gz = gx^gy
    sz = sum_g[2][gz]
    if sz:
      ans = (ans + sx*sy*sz) % M
print(ans)

Solution (Python):
from collections import defaultdict
import sys

input = lambda: sys.stdin.readline().rstrip()

def mod_inv(a):
  x1, y1, z1 = 1, 0, a
  x2, y2, z2 = 0, 1, M
  while z1 != 1:
    d, m = divmod(z2, z1)
    x1, x2 = x2-d*x1, x1
    y1, y2 = y2-d*y1, y1
    z1, z2 = m, z1
  return x1%M

def mex(s):
  for i in range(N+1):
    if i not in s:
      return i

def calc_grundy(edge):
  grundy = [{} for i in range(3)]
  sum_g = [defaultdict(int, {0:W_sum}) for i in range(3)]
  W = W_last
  for i in range(N, 0, -1):
    for g, s, e in zip(grundy, sum_g, edge):
      if i in e:
        m = mex({g.get(j, 0) for j in e[i]})
        if m:
          g[i] = m
          s[g[i]] =  (s[g[i]] + W) % M
          s[0] =  (s[0] - W) % M
    W = W * B_inv % M
  return sum_g

def read_edge():
  M = int(input())
  e = defaultdict(list)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].append(b)
  return e

N = int(input())
M = 998244353
B = pow(10, 18, M)
B_inv = mod_inv(B)
W_last = pow(B, N, M)
W_sum = (W_last - 1) * B * mod_inv(B-1) % M

edge = [read_edge() for i in range(3)]
sum_g = calc_grundy(edge)
ans = 0
for gx, sx in sum_g[0].items():
  for gy, sy in sum_g[1].items():
    gz = gx^gy
    sz = sum_g[2][gz]
    if sz:
      ans = (ans + sx*sy*sz) % M
print(ans)

Solution (Python):
from collections import defaultdict
import sys

input = lambda: sys.stdin.readline().rstrip()

def mod_inv(a):
  x1, y1, z1 = 1, 0, a
  x2, y2, z2 = 0, 1, M
  while z1 != 1:
    d, m = divmod(z2, z1)
    x1, x2 = x2-d*x1, x1
    y1, y2 = y2-d*y1, y1
    z1, z2 = m, z1
  return x1%M

def mex(s):
  for i in range(N+1):
    if i not in s:
      return i

def calc_grundy(e):
  g = {}
  for i in range(N, 0, -1):
    if i not in e:
      continue
    m = mex({g.get(j, 0) for j in e[i]})
    if m:
      g[i] = m
  return g

def sum_grundy(grundy):
  sum_g = [defaultdict(int, {0:B_sum}) for i in range(3)]
  W = 1
  for i in range(1, N+1):
    W = W * B % M
    for s, g in zip(sum_g, grundy):
      if i in g:
        s[g[i]] =  (s[g[i]] + W) % M
        s[0] =  (s[0] - W) % M
  return sum_g

def read_edge():
  M = int(input())
  e = defaultdict(list)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].append(b)
  return e

N = int(input())
M = 998244353
B = pow(10, 18, M)
B_sum = (pow(B, N+1, M) - B) * mod_inv(B-1) % M

edge = [read_edge() for i in range(3)]
grundy = list(map(calc_grundy, edge))
sum_g = sum_grundy(grundy)
ans = 0
for gx, sx in sum_g[0].items():
  for gy, sy in sum_g[1].items():
    gz = gx^gy
    sz = sum_g[2][gz]
    if sz:
      ans = (ans + sx*sy*sz) % M
print(ans)

Solution (Python):
from collections import defaultdict
import sys

input = lambda: sys.stdin.readline().rstrip()

def ext_euc(a, b):
  x1, y1, z1 = 1, 0, a
  x2, y2, z2 = 0, 1, b
  while z1 != 1:
    d, m = divmod(z2,z1)
    x1, x2 = x2-d*x1, x1
    y1, y2 = y2-d*y1, y1
    z1, z2 = m, z1
  return x1, y1

class mod_int(int):
  def __new__(cls, i=0, *args, **kwargs):
    return int.__new__(cls, i%M, *args, **kwargs)
  
  def __add__(self, x):
    return self.__class__(int.__add__(self, x))
    
  def __sub__(self, x):
    return self.__class__(int.__sub__(self, x))
    
  def __neg__(self):
    return self.__class__(int.__neg__(self, x))
  
  def __mul__(self, x):
    return self.__class__(int.__mul__(self, x))
  
  def __floordiv__(self, x):
    a, b = ext_euc(x, M)
    return self * a
  
  def __invert__(self):
    a, b = ext_euc(self, M)
    return self.__class__(a)
  
  def __pow__(self, x):
    return self.__class__(int.__pow__(self, x, M))

def mex(s):
  for i in range(N+1):
    if i not in s:
      return i

def calc_grundy(e):
  g = {}
  sum_g = defaultdict(mod_int)
  sum_g[0] = (B**(N+1) - B) // (B-1)
  prev = N
  W = B**N
  for i in range(N, 0, -1):
    if i not in e:
      continue
    m = mex({g.get(j, 0) for j in e[i]})
    if m:
      g[i] = m
      W *= B_inv**(prev-i)
      sum_g[g[i]] +=  W
      sum_g[0]  -= W
      prev, W = i, W
  
  return sum_g

def read_edge():
  M = int(input())
  e = defaultdict(list)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].append(b)
  return e

def solve(N, edge):
  sum_g = list(map(calc_grundy, edge))
  ret = mod_int(0)
  for gx, sx in sum_g[0].items():
    for gy, sy in sum_g[1].items():
      gz = gx^gy
      sz = sum_g[2][gz]
      if sz:
        ret += sx*sy*sz
  return ret


M = 998244353
B = mod_int(10) ** 18
B_inv = ~B
N = int(input())

edge = [read_edge() for i in range(3)]

print(solve(N, edge))

Solution (Python):
from collections import defaultdict
import sys

input = lambda: sys.stdin.readline().rstrip()

def ext_euc(a, b):
  x1, y1, z1 = 1, 0, a
  x2, y2, z2 = 0, 1, b
  while z1 != 1:
    d, m = divmod(z2,z1)
    x1, x2 = x2-d*x1, x1
    y1, y2 = y2-d*y1, y1
    z1, z2 = m, z1
  return x1, y1

class mod_int(int):
  def __new__(cls, i=0, *args, **kwargs):
    return int.__new__(cls, i%M, *args, **kwargs)
  
  def __add__(self, x):
    return self.__class__(int.__add__(self, x))
    
  def __sub__(self, x):
    return self.__class__(int.__sub__(self, x))
    
  def __neg__(self):
    return self.__class__(int.__neg__(self, x))
  
  def __mul__(self, x):
    return self.__class__(int.__mul__(self, x))
  
  def __floordiv__(self, x):
    a, b = ext_euc(x, M)
    return self * a
  
  def __pow__(self, x):
    return self.__class__(int.__pow__(self, x, M))

def mex(s):
  for i in range(N+1):
    if i not in s:
      return i

def calc_grundy(e):
  g = {}
  for i in range(N, 0, -1):
    if i not in e:
      continue
    m = mex({g.get(j, 0) for j in e[i]})
    if m:
      g[i] = m
  sum_g = defaultdict(mod_int)
  sum_g[0] = (B**(N+1) - B) // (B-1)
  prev = 0
  W = mod_int(1)
  for i in range(1, N+1):
    if i in g:
      W *= B**(i-prev)
      sum_g[g[i]] +=  W
      sum_g[0]  -= W
      prev, W = i, W
  
  return sum_g

def read_edge():
  M = int(input())
  e = defaultdict(list)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].append(b)
  return e

def solve(N, edge):
  sum_g = list(map(calc_grundy, edge))
  ret = mod_int(0)
  for gx, sx in sum_g[0].items():
    for gy, sy in sum_g[1].items():
      gz = gx^gy
      sz = sum_g[2][gz]
      if sz:
        ret += sx*sy*sz
  return ret


M = 998244353
B = mod_int(10) ** 18
N = int(input())

edge = [read_edge() for i in range(3)]

print(solve(N, edge))

Solution (Python):
from collections import defaultdict
import sys

input = lambda: sys.stdin.readline().rstrip()

M = 998244353
B = pow(10, 18, M)
N = int(input())

def ext_euc(a, b):
  x1, y1, z1 = 1, 0, a
  x2, y2, z2 = 0, 1, b
  while z1 != 1:
    d, m = divmod(z2,z1)
    x1, x2 = x2-d*x1, x1
    y1, y2 = y2-d*y1, y1
    z1, z2 = m, z1
  return x1, y1

def inv_mod(a, b, m):
  x, y = ext_euc(a, m)
  return (x * b % m)

def mex(s):
  for i in range(N+1):
    if i not in s:
      return i

def calc_grundy(e):
  g = {}
  sum_g = defaultdict(int)
  sum_g[0] = inv_mod(B-1, pow(B, N+1, M)-B, M)
  for i in range(N, 0, -1):
    if i not in e:
      continue
    m = mex({g.get(j, 0) for j in e[i]})
    if m:
      g[i] = m
  prev_i = 0
  W = 1
  for i in range(1, N+1):
    if i in g:
      if i-prev_i != 1:
        W = (W * pow(B, i-prev_i, M)) % M
      else:
        W = (W * B) % M
      sum_g[g[i]] = (sum_g[g[i]] + W) % M
      sum_g[0]  = (sum_g[0] - W) % M
      prev_i, W = i, W
  
  return sum_g

def read_edge():
  M = int(input())
  e = defaultdict(list)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].append(b)
  return e

def solve(N, edge):
  sum_g = list(map(calc_grundy, edge))
  ret = 0
  for gx, sx in sum_g[0].items():
    for gy, sy in sum_g[1].items():
      gz = gx^gy
      sz = sum_g[2][gz]
      if sz:
        ret = (ret + sx*sy*sz) % M
  return ret

edge = [read_edge() for i in range(3)]

print(solve(N, edge))

Solution (Python):
from collections import defaultdict
import sys

input = lambda: sys.stdin.readline().rstrip()

M = 998244353
B = pow(10, 18, M)
N = int(input())

def ext_euc(a, b):
  x1, y1, z1 = 1, 0, a
  x2, y2, z2 = 0, 1, b
  while z1 != 1:
    d, m = divmod(z2,z1)
    x1, x2 = x2-d*x1, x1
    y1, y2 = y2-d*y1, y1
    z1, z2 = m, z1
  return x1, y1

def inv_mod(a, b, m):
  x, y = ext_euc(a, m)
  return (x * b % m)

def mex(s):
  for i in range(N+1):
    if i not in s:
      return i

def calc_grundy(e):
  g = {}
  sum_g = defaultdict(int)
  sum_g[0] = inv_mod(B-1, pow(B, N+1, M)-B, M)
  for i in range(N, 0, -1):
    if i not in e:
      continue
    m = mex({g.get(j, 0) for j in e[i]})
    if m:
      g[i] = m
  prev_i = 1
  W = B
  for i in range(1, N+1):
    if i in g:
      W = (W * pow(B, i-prev_i, M)) % M
      sum_g[g[i]] = (sum_g[g[i]] + W) % M
      sum_g[0]  = (sum_g[0] - W) % M
      prev_i, W = i, W
  
  return sum_g

def read_edge():
  M = int(input())
  e = defaultdict(list)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].append(b)
  return e

def solve(N, edge):
  sum_g = list(map(calc_grundy, edge))
  ret = 0
  for gx, sx in sum_g[0].items():
    for gy, sy in sum_g[1].items():
      gz = gx^gy
      sz = sum_g[2][gz]
      if sz:
        ret = (ret + sx*sy*sz) % M
  return ret

edge = [read_edge() for i in range(3)]

print(solve(N, edge))