Problem Description

After a moment of dizziness, you find yourself sitting in the computer lab. You check the time, and it is actually the year 2202. You look around again and realize that you are in the exam room for CSP-J 2202.

Before you can figure out what is going on, you seem to hear someone whisper to you: “Want to know what happened? Then show your usual ability and get an AK on this CSP-J as well.”

Then you see that the four problems are:

1. Input a positive integer $n$, and compute $\lfloor \sqrt n \rfloor$.

2. Given a bipartite graph with $n$ vertices on the left and $n$ vertices on the right, together with its edges, compute the number of its perfect matchings. Output the answer modulo $998244353$.

3. Conway's Game of Life runs on an infinite 2D grid. Each cell is either empty or contains a cell. At each moment, one iteration is performed, with the rules shown below:
   
   Now, given the initial state, find the number of live cells after iterating $k$ times.
   ps: You can try it out here.

4. You are given an undirected graph with $n$ vertices and $m$ edges. Each vertex can be colored with one of $k$ colors, and adjacent vertices (i.e., vertices directly connected by an edge) cannot have the same color. Find the number of valid colorings, and output the answer modulo $998244353$.

“This is impossible!” You almost shout. But you notice that, only on your computer, you have the input testdata for the problem. You want to brute-force the answer, but you find that the performance of the judge machines in 2202 is no different from more than a hundred years ago.

So what should you do? In any case, you can only rely on yourself.

The input testdata can be downloaded from the attachment below the problem.

Input Format

The first line contains a positive integer $T$, which indicates the test point ID.

If $T \in \{1,2\}$, it means Subtask 1. The next line contains a single positive integer $n$.

If $T \in \{3,4,5,6\}$, it means Subtask 2. The second line contains a positive integer $n$.
Then follow $n$ lines. On the $i$-th line, first input a positive integer $m_i$, indicating that the degree of the $i$-th vertex in the left part (denoted as $u_i$) is $m_i$. Then input $m_i$ integers $v_{i,1},v_{i,2},\cdots,v_{i,m_i}$, which are the indices of vertices in the right part connected to $u_i$.

If $T \in \{7,8,9\}$, it means Subtask 3. The second line contains three positive integers $n,m,k$, meaning that the given initial pattern has $n$ rows and $m$ columns (besides this, it is an infinite 2D plane with no other cells), and it will be iterated $k$ times.
Then follow $n$ lines, each being a 01 string of length $m. 0means empty, and1` means a live cell, describing one row of the pattern.

If $T \in \{10,11,12\}$, it means Subtask 4. The second line contains three positive integers $n,m,k$.
Then follow $m$ lines, each containing two positive integers $u,v$ describing an undirected edge. It is guaranteed that there are no multiple edges and no self-loops.

Output Format

Output one line containing a positive integer, which is the answer.

3
3
2 1 2
2 2 3
2 1 3

2

7
5 5 133
10001
00000
11111
00000
01010

129

Hint

[Sample $1$ Explanation]
In the input, $T=3$, so the required task is counting perfect matchings in a bipartite graph.
It can be seen that there are only two matching schemes: $1 \leftrightarrow 1,2 \leftrightarrow 2,3 \leftrightarrow 3$ or $1 \leftrightarrow 2,2 \leftrightarrow 3,3 \leftrightarrow 1$.

[Sample $2$ Explanation]
In the input, $T=7$, so the required task is predicting the number of live cells in the Game of Life. The given input is:

After $133$ iterations, it becomes:

You can count that the number of live cells is $129$.

Although the samples have $T \in [1,12]$, this does not represent the actual input.

[Test Point Score Information]

Translated by ChatGPT 5