给您一个二部图,第一部分有 $$$n_1$$$ 个顶点,第二部分有 $$$n_2$$$ 个顶点,以及 $$$m$$$ 个边。该图中的最大匹配是该图的边的最大可能(按大小)子集,使得没有顶点与多个选定边相关。
您必须处理对此图的两种类型的查询:
- $$$1$$$ — 从此图中删除尽可能少的顶点数,以便最大匹配的大小恰好减少 $$$1$$$,并打印已删除的顶点。然后,找到该图中的任何最大匹配并打印属于该匹配的边的索引之和;
- $$$2$$$ — 仅在 $$$1$$$ 类型的查询之后才会询问此类型的查询。作为此查询的答案,您必须打印形成您在上一个查询中选择的最大匹配的边。
请注意,您应该以在线模式解决该问题。这意味着您无法一次读取整个输入。您只有在写完最后一个查询的答案后才能阅读每个查询。每次编写程序后,请使用 C++ 中的 fflush 函数和 Java 语言中的 BufferedWriter.flush 函数。
输入
第一行包含四个整数 $$$n_1$$$、$$$n_2$$$、$$$m$$$ 和 $$$q$$$ ($$$1 \le n_1, n_2 \le 2 \cdot 10^5$$$; $$$1 \le m \le \min(n_1 \cdot n_2, 2 \cdot 10^5)$$$; $$$1 \le q \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$$$ 行。其中第 $$$i$$$ 包含一个整数,$$$1$$$ 或 $$$2$$$,表示第 $$$i$$$ 查询。对查询的附加限制:
- $$$1$$$ 类型的查询数量不会超过初始图中最大匹配的大小;
- $$$2$$$类型的查询数量不会超过$$$3$$$;
- 每个 $$$2$$$ 类型的查询前面都有一个 $$$1$$$ 类型的查询;
- 只有在打印第 $$$(i-1)$$$ 个查询的答案并刷新输出后,您的解决方案才允许读取第 $$$i$$$ 个查询。
输出
对于 $$$1$$$ 类型的查询,按三行打印答案,如下所示:
- 第一行应包含您删除的顶点数;
- 第二行应包含您删除的顶点的索引,如下所示:如果您从左侧删除顶点 $$$x$$$,则打印 $$$x$$$;如果从右侧删除顶点$$$y$$$,则打印$$$-y$$$(负索引);
- 第三行应包含结果图中某些最大匹配的边索引之和。边的编号从 $$$1$$$ 到 $$$m$$$。
对于 $$$2$$$ 类型的查询,以两行打印答案,如下所示:
- 第一行应包含最大匹配的大小;
- 第二行应包含属于最大匹配的边的索引。请注意,这些索引的总和应等于您在 $$$1$$$ 类型的上一个查询末尾打印的数字;
打印查询的答案后,不要忘记刷新输出。
示例
输入 #1
3 4 4 4 2 2 1 3 2 1 3 4 1 2 1 2
输出 #1
1 -4 3 === 2 1 2 === 1 2 2 === 1 2
注意
在此问题中,由于处于在线模式,您可能会收到“超出空闲限制”的判决。如果发生这种情况,则意味着输出格式错误,或者不满足问题的某些约束。您可以将此判断视为“错误答案”。
为了您的方便,示例中查询的输出由 === 行分隔。不要在程序中打印此行,这样做只是为了确保可以轻松区分语句中不同查询的答案。