CF1499G Graph Coloring

给定一个二分图，第一部分有 $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\ v_1\ v_2$ —— 添加一条新边，将第一部分的顶点 $v_1$ 与第二部分的顶点 $v_2$ 连接起来。这条边的编号为：第一条新增边编号为 $m+1$，第二条为 $m+2$，以此类推。添加边后，你需要输出当前最优染色的哈希值（如果存在多个最优染色，输出任意一个的哈希值即可）。实际上，这个哈希值不会被验证，你可以输出任意一个数字作为该操作的答案，但你可能会被要求给出具有该哈希值的染色方案； - $2$ —— 输出哈希值与上一次操作输出相同的最优染色方案。此类操作只会在上一次操作为类型 $1$ 时出现，且此类操作最多只会有 $10$ 次。如果存在多个最优染色方案对应该哈希值，输出任意一个即可。 注意，如果某条边在某次染色中为红色或蓝色，在之后的染色中它的颜色可能会发生变化。 染色的哈希值计算方式如下：设 $R$ 为所有红色边的编号集合，则哈希值为 $(\sum\limits_{i \in R} 2^i) \bmod 998244353$。 注意，你需要以在线模式解决本题。这意味着你不能一次性读入所有输入数据。你只能在输出上一次操作的答案后，才能读取下一条操作。请在每次输出后使用 C++ 的 fflush 或 Java 的 BufferedWriter.flush 进行刷新。

第一行包含三个整数 $n_1$、$n_2$ 和 $m$（$1 \le n_1, n_2, m \le 2 \times 10^5$）。 接下来 $m$ 行，每行包含两个整数 $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 \times 10^5$），表示你需要处理的操作数量。 接下来的 $q$ 行，每行表示一个操作，格式见题目描述。 输入的额外约束： - 任意时刻，图中都不会有重边； - 类型 $2$ 的操作只会在上一次操作为类型 $1$ 时出现； - 类型 $2$ 的操作最多只有 $10$ 次。

对于类型 $1$ 的操作，输出一个整数，表示最优染色的哈希值。 对于类型 $2$ 的操作，输出一行。首先输出一个整数 $k$，表示红色边的数量。接着输出 $k$ 个不同的整数，表示红色边的编号，顺序任意。每个编号都应对应一条已存在的边，且你输出的染色方案的哈希值应等于上一次操作输出的哈希值。 如果有多种答案，输出任意一种均可。

由 ChatGPT 4.1 翻译