← 返回题目列表

Codeforces · 1499/G

G. 图形着色

中文机器翻译题面 查看原题

给您一个二部图,由第一部分中的 $$$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 \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$$$;
- 最多有 $$$10$$$ 类型为 $$$2$$$ 的查询。

输出

要回答 $$$1$$$ 类型的查询,请打印一个整数 - 最佳着色的哈希值。

要回答 $$$2$$$ 类型的查询,请打印一行。它应该以整数 $$$k$$$ 开头——红边的数量。然后,后面应该是 $$$k$$$ 不同的整数 - 颜色中红色边缘的索引,顺序任意。每个索引应该对应于一个现有的边,并且您生成的着色的哈希值应该等于您作为上一个查询的答案打印的哈希值。

如果查询有多个答案,您可以打印其中任何一个。

示例

输入 #1

3 4 2
1 2
3 4
10
1 1 3
1 2 3
2
1 3 3
2
1 2 4
2
1 2 1
1 1 1
2

输出 #1

8
8
1 3
40
2 3 5
104
3 5 6 3
104
360
4 5 6 3 8