Graph Coloring
Contest: Educational Codeforces Round 106 (Rated for Div. 2)
Difficulty rating: 3100
Tags: data structures, graphs, interactive

You are given a bipartite graph consisting of $$$n_1$$$ vertices in the first part, $$$n_2$$$ vertices in the second part, and $$$m$$$ edges, numbered from $$$1$$$ to $$$m$$$. You have to color each edge into one of two colors, red and blue. You have to minimize the following value: $$$\sum \limits_{v \in V} |r(v) - b(v)|$$$, where $$$V$$$ is the set of vertices of the graph, $$$r(v)$$$ is the number of red edges incident to $$$v$$$, and $$$b(v)$$$ is the number of blue edges incident to $$$v$$$.

Sounds classical and easy, right? Well, you have to process $$$q$$$ queries of the following format:

- $$$1$$$ $$$v_1$$$ $$$v_2$$$ — add a new edge connecting the vertex $$$v_1$$$ of the first part with the vertex $$$v_2$$$ of the second part. This edge gets a new index as follows: the first added edge gets the index $$$m + 1$$$, the second — $$$m + 2$$$, and so on. After adding the edge, you have to print the hash of the current optimal coloring (if there are multiple optimal colorings, print the hash of any of them). Actually, this hash won't be verified, you may print any number as the answer to this query, but you may be asked to produce the coloring having this hash;
- $$$2$$$ — print the optimal coloring of the graph with the same hash you printed while processing the previous query. The query of this type will only be asked after a query of type $$$1$$$, and there will be at most $$$10$$$ queries of this type. If there are multiple optimal colorings corresponding to this hash, print any of them.

Note that if an edge was red or blue in some coloring, it may change its color in next colorings.

The hash of the coloring is calculated as follows: let $$$R$$$ be the set of indices of red edges, then the hash is $$$(\sum \limits_{i \in R} 2^i) \bmod 998244353$$$.

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 three integers $$$n_1$$$, $$$n_2$$$ and $$$m$$$ ($$$1 \le n_1, n_2, m \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$$$ from the first part and the vertex $$$y_i$$$ from the second part.

The next line contains one integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of queries you have to process.

The next $$$q$$$ lines contain the queries in the format introduced in the statement.

Additional constraints on the input:

- at any moment, the graph won't contain any multiple edges;
- the queries of type $$$2$$$ are only asked if the previous query had type $$$1$$$;
- there are at most $$$10$$$ queries of type $$$2$$$.

Output format:
To answer a query of type $$$1$$$, print one integer — the hash of the optimal coloring.

To answer a query of type $$$2$$$, print one line. It should begin with the integer $$$k$$$ — the number of red edges. Then, $$$k$$$ distinct integer should follow — the indices of red edges in your coloring, in any order. Each index should correspond to an existing edge, and the hash of the coloring you produce should be equal to the hash you printed as the answer to the previous query.

If there are multiple answers to a query, you may print any of them.

Constraints:
Time limit: 7.0 s
Memory limit: 1024.0 MB

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

Example output:
8
8
1 3
40
2 3 5
104
3 5 6 3
104
360
4 5 6 3 8

Editorial:
Let's split all edges of the graph into several paths and cycles (each edge will belong to exactly one path or cycle). Each path and each cycle will be colored in an alternating way: the first edge will be red, the second — blue, the third — red, and so on (or vice versa). Since the graph is bipartite, each cycle can be colored in an alternating way. The main idea of the solution is to add the edges one by one, maintain the structure of cycles and paths, and make sure that for each vertex, at most one path starts/ends in it. If we are able to maintain this invariant, then the value of $$$|r(v) - b(v)|$$$ for every vertex will be minimum possible — each cycle going through a vertex covers an even number of edges incident to it (half of them will be red, half of them will be blue); so, if the degree of a vertex is odd, one path will have this vertex as an endpoint, and $$$|r(v) - b(v)| = 1$$$; otherwise, it won't be an endpoint of any path, so $$$|r(v) - b(v)| = 0$$$.
Okay, how do we maintain this structure? Let's add edges one by one (even the original edges of the graph) and rebuild the structure in online mode. For each vertex, we will maintain the indices of the paths that have this vertex as an endpoint. If some vertex has $$$2$$$ or more paths as its endpoints, we can choose two of them and link them together. Whenever we add an edge from $$$x$$$ to $$$y$$$, we just create a new path and check if we can link together some paths that have $$$x$$$ or $$$y$$$ as their endpoints.
How do we link the paths together? If we try to link a path with itself, it means that we try to close a cycle — and when we do it, we just forget about the resulting cycle, its structure won't change in future queries. When we link a path with some other path, we might need to reverse and/or repaint the paths before merging them into one. There are (at least) two possible data structures we can use to do this:
• either an implicit-key treap that supports reversing and repainting;
• or a deque with small-to-large merging: whenever we try to link two paths together, we repaint and/or reverse the smaller one.
Both of those methods give a solution in $$$O((m + q) \log(m + q))$$$ or $$$O((m + q) \log^2(m + q))$$$, depending on your implementation. The model solution uses deques and small-to-large merging.