Matching Reduction
Contest: Educational Codeforces Round 134 (Rated for Div. 2)
Difficulty rating: 2800
Tags: brute force, constructive algorithms, dfs and similar, flows, graph matchings, graphs, interactive

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.

Input format:
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.

Output format:
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.

Constraints:
Time limit: 8.0 s
Memory limit: 512.0 MB

Note:
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.

Example input:
3 4 4 4
2 2
1 3
2 1
3 4
1
2
1
2

Example output:
1
-4
3
===
2
1 2
===
1
2
2
===
1
2

Editorial:
Let's start by finding the maximum matching in the given graph. Since the constraints are pretty big, you need something fast. The model solution converts the matching problem into a flow network and uses Dinic to find the matching in $$$O(m^{1.5})$$$, but something like heavily optimized Kuhn's algorithm can also work.
Okay, then what about finding the minimum possible number of vertices to delete in order to reduce the maximum matching? We claim that it is always enough to remove one vertex, and the proof will also provide a way to quickly search for such vertices.
Let's recall that the size of the maximum matching is equal to the size of the minimum vertex cover (this only works in bipartite graphs). So, we will try to find a way to reduce the minimum vertex cover by $$$1$$$, and it's actually pretty easy — just remove any vertex belonging to the vertex cover; it's obvious that it reduces the vertex cover by $$$1$$$, and the maximum matching by $$$1$$$ as well. So, we can find the minimum vertex cover in the graph using the standard algorithm to convert the MM into MVC (or, if you're using Dinic to find the maximum matching, you can represent the minimum vertex cover as the minimum cut problem), and for each query of type $$$1$$$, just take a vertex from the vertex cover we found.
Now the only thing that's left is discussing how to maintain the structure of the maximum matching in the graph. In fact, it's quite easy:
• on the one hand, since we remove the vertices belonging to the minimum vertex cover, every edge (including the edges from the matching) will be incident to one of the vertices we will remove;
• on the other hand, due to the definition of the maximum matching, there is no vertex that is incident to two or more edges from the maximum matching;
• so, every vertex from the vertex cover has exactly one edge from the maximum matching that is incident to it, and when we remove a vertex, we can simply remove the corresponding edge from the maximum matching.
So, the only thing we need to do is to maintain which edge from the matching corresponds to which vertex from the minimum vertex cover, and it will allow us to maintain the structure of the maximum matching — and since these "pairs" don't change when we remove a vertex, it is enough to get this information right after we have constructed the maximum matching in the given graph; we won't need to rebuild it.