P8562 十二重骗分法（Cheating XII）

一阵恍惚过后，你发现自己坐在机房里。一看时间，现在竟然是 2202 年！你又环视了一下周围的情况，原来自己在 CSP-J 2202 的考场上。 你还没搞清楚情况时，似乎听见有人对你低语：「想知道怎么回事吗？那就展现你以往的能力，把这次的 CSP-J 也 AK 掉吧。」 于是你看到四个题分别是： 1. 输入一个正整数 $n$，求 $\lfloor \sqrt n \rfloor$。 2. 给定一个左右各有 $n$ 个点的二分图，与其中的边，求它完美匹配的方案数，答案对 $998244353$ 取模。 3. 生命游戏（Conway's Game of Life）进行于一个无限大的二维网格上，每个格子要么是空地，要么有一个细胞。每个时刻都会进行一轮**迭代**，规则如下：  现在，给定你初始状态，求迭代 $k$ 次后的细胞数。 ps：你可以在 [这里](https://playgameoflife.com/) 试玩。 4. 给你一个 $n$ 个点、 $m$ 条边的无向图，每个点都可以涂上 $k$ 种颜色中的一种，且相邻的点（即有边直接相连的点）不能有相同的颜色。求有多少种染色方案，答案对 $998244353$ 取模。 「这怎么可能啊！」你差点惊叫出来。不过你发现，唯独你的电脑上有题目的输入数据！你想暴力跑出答案，却发现 2202 年的评测机性能和一百多年前没差别。 那该怎么办呢？总之只能靠自己了吧。 **输入数据可以在题目下方的附件中下载。**

第一行一个正整数 $T$，表示测试点编号。 若 $T \in \{ 1,2\}$，表示 Subtask 1。接下来一行仅一个正整数 $n$。 若 $T \in \{3,4,5,6\}$，表示 Subtask 2。第二行一个正整数 $n$。 接下来 $n$ 行，第 $i$ 行先输入一个正整数 $m_i$，表示左部分第 $i$ 个点（记作 $u_i$）的度数为 $m_i$；后面接着 $m_i$ 个整数 $v_{i,1},v_{i,2},\cdots,v_{i,m_i}$，依次表示与 $u_i$ 连接的右部分节点编号。 若 $T \in\{ 7,8,9\}$，表示 Subtask 3。第二行输入三个正整数 $n,m,k$，表示输入的初始形态有 $n$ 行 $m$ 列（除此之外是无限大的二维平面，没有其它细胞），迭代 $k$ 次。接下来 $n$ 行，每行一个长度为 $m$ 的 01 串，`0` 表示空地，`1` 表示细胞，描述了一行的形态。 若 $T \in\{ 10,11,12\}$，表示 Subtask 4。第二行输入三个正整数 $n,m,k$。接下来 $m$ 行，每行两个正整数 $u,v$ 描述一条无向边，保证无重边和自环。

输出一行一个正整数，表示答案。

【样例 $1$ 解释】 输入中 $T=3$，要求的问题是二分图完美匹配计数。 可以发现，只有两种匹配方案：$1 \leftrightarrow 1,2 \leftrightarrow 2,3 \leftrightarrow 3$ 或 $1 \leftrightarrow 2,2 \leftrightarrow 3,3 \leftrightarrow 1$。 【样例 $2$ 解释】 输入中 $T=7$，要求的问题是预测生命游戏细胞数。给出的输入是：  经过 $133$ 轮迭代后为：  可以数出其中细胞数为 $129$。 样例中虽然有 $T\in[1,12]$，但并不代表实际输入。 【测试点分数信息】 | 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | | **分数** | $7$ | $8$ | $6$ | $7$ | $9$ | $11$ | $8$ | $9$ | $10$ | $7$ | $8$ | $10$ |