CF1499G.Graph Coloring

You are given a bipartite graph consisting of $n_1$ vertices in the first part, $n_2$ vertices in the second part, and $m$ edges, numbered from $1$ to $m$. You have to color each edge into one of two colors, red and blue. You have to minimize the following value: $\sum \limits_{v \in V} |r(v) - b(v)|$, where $V$ is the set of vertices of the graph, $r(v)$ is the number of red edges incident to $v$, and $b(v)$ is the number of blue edges incident to $v$.

Sounds classical and easy, right? Well, you have to process $q$ queries of the following format:

• $1$ $v_1$ $v_2$ — add a new edge connecting the vertex $v_1$ of the first part with the vertex $v_2$ of the second part. This edge gets a new index as follows: the first added edge gets the index $m + 1$, the second — $m + 2$, and so on. After adding the edge, you have to print the hash of the current optimal coloring (if there are multiple optimal colorings, print the hash of any of them). Actually, this hash won't be verified, you may print any number as the answer to this query, but you may be asked to produce the coloring having this hash;
• $2$ — print the optimal coloring of the graph with the same hash you printed while processing the previous query. The query of this type will only be asked after a query of type $1$, and there will be at most $10$ queries of this type. If there are multiple optimal colorings corresponding to this hash, print any of them.

Note that if an edge was red or blue in some coloring, it may change its color in next colorings.

The hash of the coloring is calculated as follows: let $R$ be the set of indices of red edges, then the hash is $(\sum \limits_{i \in R} 2^i) \bmod 998244353$.

Note that you should solve the problem in online mode. It means that you can't read the whole input at once. You can read each query only after writing the answer for the last query. Use functions fflush in C++ and BufferedWriter.flush in Java languages after each writing in your program.

你被给定一个二分图，其中第一部分包含 $n_1$ 个顶点，第二部分包含 $n_2$ 个顶点，共有 $m$ 条边，编号从 $1$ 到 $m$。你需要将每条边染成两种颜色之一：红色或蓝色。目标是最小化如下值：

$$\sum \limits_{v \in V} |r(v) - b(v)|,$$

其中 $V$ 是图的顶点集，$r(v)$ 表示与顶点 $v$ 关联的红色边的数量，$b(v)$ 表示与顶点 $v$ 关联的蓝色边的数量。

听起来很经典、很简单，对吧？但事实上，你需要处理 $q$ 个如下格式的查询：

• 1 v1 v2 — 添加一条新边，连接第一部分的顶点 $v_1$ 和第二部分的顶点 $v_2$。该边获得一个新的编号：第一个添加的边编号为 $m + 1$，第二个为 $m + 2$，依此类推。添加该边后，你必须输出当前最优染色方案的哈希值（若存在多个最优染色方案，则输出其中任意一个的哈希值）。实际上，该哈希值不会被验证，你可对这一查询输出任意整数作为答案；但后续可能要求你构造出具有该哈希值的染色方案；
• 2 — 输出当前图的一个最优染色方案，其哈希值需与上一次类型 1 查询中输出的哈希值相同。此类查询仅在上一次查询为类型 1 后出现，且最多出现 $10$ 次。若存在多个对应于该哈希值的最优染色方案，则输出其中任意一个即可。

注意：若某条边在某个染色方案中为红色（或蓝色），它在后续的染色方案中可能变为蓝色（或红色）。

染色方案的哈希值定义如下：设 $R$ 为所有红色边的编号构成的集合，则哈希值为

$$\left(\sum \limits_{i \in R} 2^i\right) \bmod 998244353.$$

注意：你需要以在线模式求解本题。这意味着你不能一次性读入全部输入。你只能在输出上一查询的答案之后，才能读入下一个查询。在 C++ 中，请使用 fflush 函数；在 Java 中，请使用 BufferedWriter.flush 方法，在每次输出后刷新输出缓冲区。

The first line contains three integers $n_1$, $n_2$ and $m$ ($1 \le n_1, n_2, m \le 2 \cdot 10^5$).

Then $m$ lines follow, the $i$-th of them contains two integers $x_i$ and $y_i$ ($1 \le x_i \le n_1$; $1 \le y_i \le n_2$) meaning that the $i$-th edge connects the vertex $x_i$ from the first part and the vertex $y_i$ from the second part.

The next line contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of queries you have to process.

The next $q$ lines contain the queries in the format introduced in the statement.

Additional constraints on the input:

• at any moment, the graph won't contain any multiple edges;
• the queries of type $2$ are only asked if the previous query had type $1$;
• there are at most $10$ queries of type $2$.

第一行包含三个整数 $n_1$、$n_2$ 和 $m$（$1 \le n_1, n_2, m \le 2 \cdot 10^5$）。

接下来 $m$ 行，其中第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i \le n_1$；$1 \le y_i \le n_2$），表示第 $i$ 条边连接第一部分中的顶点 $x_i$ 和第二部分中的顶点 $y_i$。

下一行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$）—— 表示你需要处理的查询数量。

接下来的 $q$ 行按题目描述中规定的格式给出查询。

输入的额外约束条件：

• 在任意时刻，图中均不包含重边；
• 类型为 $2$ 的查询仅在前一个查询类型为 $1$ 时才会出现；
• 类型为 $2$ 的查询至多有 $10$ 个。

To answer a query of type $1$, print one integer — the hash of the optimal coloring.

To answer a query of type $2$, print one line. It should begin with the integer $k$ — the number of red edges. Then, $k$ distinct integer should follow — the indices of red edges in your coloring, in any order. Each index should correspond to an existing edge, and the hash of the coloring you produce should be equal to the hash you printed as the answer to the previous query.

If there are multiple answers to a query, you may print any of them.

对于类型为 $1$ 的查询，输出一个整数——最优染色方案的哈希值。

对于类型为 $2$ 的查询，输出一行。该行应以整数 $k$ 开头——即红色边的数量；随后是 $k$ 个互不相同的整数——即你所构造的染色方案中红色边的编号（顺序任意）。每个编号必须对应一条实际存在的边，且你所构造的染色方案的哈希值应等于你在上一个查询中输出的哈希值。

若某个查询存在多个合法答案，你可以输出其中任意一个。