AtCoder Grand Contest 043 - Giant Graph

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.

Examples

Input

2
1
1 2
1
1 2
1
1 2


Output

46494701


Input

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


Output

883188316


Input

100000
1
1 2
1
99999 100000
1
1 100000


Output

318525248

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
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)


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)


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)


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

def calc():

	def mex(i):
		t = 0
		for j in X[i]:
			t |= 1 << G[j]
		t = ~t
		return (t & -t).bit_length() - 1
	M = int(input())
	X = [[] for _ in range(N)]
	for _ in range(M):
		(a, b) = map(int, input().split())
		X[N - min(a, b)].append(N - max(a, b))
	G = [0] * N
	for i in range(N):
		G[i] = mex(i)
	H = [0] * 1024
	a = 1
	for i in range(N)[::-1]:
		a = a * A % P
		H[G[i]] = (H[G[i]] + a) % P
	return H
P = 998244353
A = pow(10, 18, P)
N = int(input())
(H1, H2, H3) = (calc(), calc(), calc())
ans = 0
for i in range(1024):
	if H1[i] == 0:
		continue
	for j in range(1024):
		if H2[j] == 0:
			continue
		ans = (ans + H1[i] * H2[j] * H3[i ^ j]) % P
print(ans)


from collections import defaultdict
M = 998244353
B = 10 ** 18 % M

def mex(s):
	for i in range(max(s) + 2):
		if i not in s:
			return i

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 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 sorted(e.keys(), reverse=True):
		m = mex({g.get(j, 0) for j in e[i]})
		if m:
			g[i] = m
			x = pow(B, i, M)
			sum_g[m] += x
			sum_g[0] -= x
	return sum_g

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

def solve(N, edge):
	sum_g = list(map(calc_grundy, edge))
	ret = 0
	for (gx, x) in sum_g[0].items():
		for (gy, y) in sum_g[1].items():
			gz = gx ^ gy
			z = sum_g[2][gz]
			ret = (ret + x * y * z) % M
	return ret
N = int(input())
edge = [get_edge() for i in range(3)]
print(solve(N, edge))


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))


from collections import defaultdict
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 = {}
	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(int)
	sum_g[0] = inv_mod(B - 1, pow(B, N + 1, M) - B, M)
	x = 1
	for i in range(1, N + 1):
		x = x * B % M
		if i in g:
			j = g.pop(i)
			sum_g[j] = (sum_g[j] + x) % M
			sum_g[0] = (sum_g[0] - x) % M
			if not g:
				break
	return sum_g

def read_edge():
	M = int(input())
	e = defaultdict(set)
	for i in range(M):
		(a, b) = sorted(map(int, input().split()))
		e[a].add(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 += sx * sy * sz % M
	return ret % M
edge = [read_edge() for i in range(3)]
print(solve(N, edge))


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)


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))


def calc():

	def mex(i):
		D = {}
		for j in X[i]:
			D[G[j]] = 1
		for g in range(N + 1):
			if g not in D:
				return g
	M = int(input())
	X = [[] for _ in range(N)]
	for _ in range(M):
		(a, b) = map(int, input().split())
		X[N - min(a, b)].append(N - max(a, b))
	G = [0] * N
	for i in range(N):
		G[i] = mex(i)
	H = [0] * 1024
	a = 1
	for i in range(N)[::-1]:
		a = a * A % P
		H[G[i]] = (H[G[i]] + a) % P
	return H
P = 998244353
A = pow(10, 18, P)
N = int(input())
(H1, H2, H3) = (calc(), calc(), calc())
ans = 0
for i in range(1024):
	if H1[i] == 0:
		continue
	for j in range(1024):
		if H2[j] == 0:
			continue
		ans = (ans + H1[i] * H2[j] * H3[i ^ j]) % P
print(ans)


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)


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)


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)
main()


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)