CF1721F.Matching Reduction

You are given a bipartite graph with $n_1$ vertices in the first part, $n_2$ vertices in the second part, and $m$ edges. The maximum matching in this graph is the maximum possible (by size) subset of edges of this graph such that no vertex is incident to more than one chosen edge.

You have to process two types of queries to this graph:

• $1$ — remove the minimum possible number of vertices from this graph so that the size of the maximum matching gets reduced exactly by $1$, and print the vertices that you have removed. Then, find any maximum matching in this graph and print the sum of indices of edges belonging to this matching;
• $2$ — query of this type will be asked only after a query of type $1$. As the answer to this query, you have to print the edges forming the maximum matching you have chosen in the previous query.

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$ — 从图中移除最少可能数量的顶点，使得最大匹配的大小恰好减少 $1$，并输出你所移除的顶点；然后，在该图中找出任意一个最大匹配，并输出该匹配中所有边的下标之和；
• $2$ — 此类查询仅在一次类型 $1$ 的查询之后出现。作为该查询的答案，你需要输出上一次类型 $1$ 查询中你所选定的那个最大匹配所包含的各条边。

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

The first line contains four integers $n_1$, $n_2$, $m$ and $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$).

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$ in the first part and the vertex $y_i$ in the second part. There are no pairs of vertices that are connected by more than one edge.

Then $q$ lines follow. The $i$-th of them contains one integer, $1$ or $2$, denoting the $i$-th query. Additional constraints on queries:

• the number of queries of type $1$ won't exceed the size of the maximum matching in the initial graph;
• the number of queries of type $2$ won't exceed $3$;
• each query of type $2$ is preceded by a query of type $1$;
• your solution is allowed to read the $i$-th query only after printing the answer for the $(i-1)$-th query and flushing the output.

第一行包含四个整数 $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$ 个查询。

For a query of type $1$, print the answer in three lines as follows:

• the first line should contain the number of vertices you remove;
• the second line should contain the indices of vertices you remove, as follows: if you remove the vertex $x$ from the left part, print $x$; if you remove the vertex $y$ from the right part, print $-y$ (negative index);
• the third line should contain the sum of indices of edges in some maximum matching in the resulting graph. The edges are numbered from $1$ to $m$.

For a query of type $2$, print the answer in two lines as follows:

• the first line should contain the size of the maximum matching;
• the second line should contain the indices of the edges belonging to the maximum matching. Note that the sum of these indices should be equal to the number you printed at the end of the previous query of type $1$;

After printing the answer to a query, don't forget to flush the output.

对于类型为 $1$ 的查询，按以下格式分三行输出答案：

• 第一行应包含你所删除的顶点数量；
• 第二行应包含你所删除的顶点的下标，规则如下：若你从左部删除顶点 $x$，则输出 $x$；若你从右部删除顶点 $y$，则输出 $-y$（负号表示下标）；
• 第三行应包含剩余图中某个最大匹配所含边的下标之和。边的下标从 $1$ 到 $m$ 编号。

对于类型为 $2$ 的查询，按以下格式分两行输出答案：

• 第一行应包含最大匹配的大小（即边数）；
• 第二行应包含属于该最大匹配的各条边的下标。注意：这些下标之和必须等于上一个类型为 $1$ 的查询中第三行所输出的数值。

在输出每个查询的答案后，请务必刷新输出缓冲区。

In this problem, you may receive the verdict "Idleness Limit Exceeded" since it is in online mode. If it happens, it means that either the output format is wrong, or you don't meet some constraint of the problem. You may treat this verdict as "Wrong Answer".

For your convenience, the output for queries in the example is separated by the line ===. Don't print this line in your program, it is done only to make sure that it's easy to distinguish between answers for different queries in the statement.

本题为在线评测模式，你可能会收到 “空闲时间超限（Idleness Limit Exceeded）” 的判题结果。若发生此情况，说明你的输出格式有误，或未满足题目中的某些约束条件。你可以将该判题结果视作“答案错误（Wrong Answer）”。

为便于理解，示例中各查询的输出用一行 \=== 分隔。请勿在你的程序中输出该行——它仅用于在题目描述中清晰区分不同查询所对应的回答。