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:
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.
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:
For a query of type $$$1$$$, print the answer in three lines as follows:
For a query of type $$$2$$$, print the answer in two lines as follows:
After printing the answer to a query, don't forget to flush the output.
3 4 4 4 2 2 1 3 2 1 3 4 1 2 1 2
1 -4 3 === 2 1 2 === 1 2 2 === 1 2
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.