题目描述

$k$ 维生物居住在 $k$ 维空间里的一张点数为 $n^k$ 的无向图 $G$ 上，$G$ 的顶点用 $\textbf{x}=(x_1,x_2,\cdots,x_k)$ 表示，其中 $x_i\in [1, n] \cap \mathbb{Z}$。

同时给定 $k$ 张无向图，图从 $1$ 到 $k$ 编号，其中图 $G_i=(\{1,2,\cdots,n\},E_i)$，$|E_i|=m_i$。

对于图 $G$ 的两个不同的顶点 $\textbf{x}$ 和 $\textbf{y}$，两者有边当且仅当两者恰好只有第 $i$ 维的分量 $x_i$ 和 $y_i$ 不同，且满足 $(x_i,y_i)\in E_i$。

$k$ 维生物喜欢做游戏，游戏是和独立集有关的。现在他们想和你做游戏：假设图 $G$ 中顶点 $\textbf{x}$ 的 点权为 $V^{\sum_{i=1}^kx_i}$，其中 $V$ 比你能想象到的最大的数还要大，求这张图最大权独立集的权值，答案对 $998244353$ 取模。

输入格式

第一行三个整数 $n,k,v$，含义与题面一致，其中 $v$ 表示为 $V \bmod 998244353$ 的值。

接下来按顺序依次给定 $k$ 张无向图，每张图按如下方式给出：首先给出 $m_i$，表示 $G_i$ 的边集大小，之后的 $m_i$ 行中，第 $j$ 行有两个正整数 $u_j,v_j$，表示 $G_i$ 的一条无向边 $(u_j,v_j)$。

输出格式

输出一个整数，表示图 $G$ 最大权独立集的权值对 $998244353$ 取模后的值。

样例

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

4

5 1 2
4
4 2
3 5
1 3
3 4

50

10 5 402600065
0
0
0
0
0

416675831

见附加文件 game4.in

见附加文件 game4.out

最大权独立集为 $\{(2, 1, 1),(1, 2, 1),(1, 1, 2),(2, 2, 2)\}$。

数据范围

对于所有数据，$1\le n \le 10^5$，$1 \le k \le 5$，$1 \le v \le 998244352$，保证：

• $0 \le m_i \le \min(\binom{n}{2},10^5)$；

• $1 \le u_j,v_j \le n$；

• 给定的图 $G_i$ 无重边无自环，不保证联通。

详细测试点及附加限制如下表所示：