CF1721F Matching Reduction

给定一个二分图，第一部分有 $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 \times 10^5$；$1 \le m \le \min(n_1 \times n_2, 2 \times 10^5)$；$1 \le q \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$ 或 $2$，表示第 $i$ 个查询。关于查询的额外约束如下： - 类型为 $1$ 的查询次数不会超过初始图的最大匹配大小； - 类型为 $2$ 的查询次数不会超过 $3$； - 每个类型为 $2$ 的查询前面必定有一个类型为 $1$ 的查询； - 你的程序只能在输出第 $(i-1)$ 个查询的答案并刷新输出后，才能读取第 $i$ 个查询。

对于类型为 $1$ 的查询，输出三行： - 第一行输出你删除的顶点数； - 第二行输出你删除的顶点编号：如果删除的是左部的顶点 $x$，输出 $x$；如果删除的是右部的顶点 $y$，输出 $-y$（负号表示右部顶点）； - 第三行输出在当前图中某个最大匹配的所有边的编号之和。边的编号为 $1$ 到 $m$。 对于类型为 $2$ 的查询，输出两行： - 第一行输出最大匹配的大小； - 第二行输出该最大匹配中所有边的编号。注意，这些编号之和应等于你在上一次类型为 $1$ 的查询中输出的数字。 每次输出答案后，别忘了刷新输出缓冲区。

在本题中，你可能会收到“Idleness Limit Exceeded” 的判定，因为本题为在线模式。如果出现这种情况，说明你的输出格式有误，或者没有满足题目的某些约束。你可以将其视为“答案错误”。 为方便起见，示例中的不同查询输出之间用了一行 === 分隔。你的程序中不要输出这行，这只是为了让题面更易于区分各个查询的答案。 由 ChatGPT 4.1 翻译