Perfect Matching
Contest: Educational Codeforces Round 122 (Rated for Div. 2)
Difficulty rating: 2800
Tags: data structures, divide and conquer, interactive, trees

You are given a tree consisting of $$$n$$$ vertices (numbered from $$$1$$$ to $$$n$$$) and $$$n-1$$$ edges (numbered from $$$1$$$ to $$$n-1$$$). Initially, all vertices except vertex $$$1$$$ are inactive.

You have to process queries of three types:

- $$$1$$$ $$$v$$$ — activate the vertex $$$v$$$. It is guaranteed that the vertex $$$v$$$ is inactive before this query, and one of its neighbors is active. After activating the vertex, you have to choose a subset of edges of the tree such that each active vertex is incident to exactly one chosen edge, and each inactive vertex is not incident to any of the chosen edges — in other words, this subset should represent a perfect matching on the active part of the tree. If any such subset of edges exists, print the sum of indices of edges in it; otherwise, print $$$0$$$.
- $$$2$$$ — queries of this type will be asked only right after a query of type $$$1$$$, and there will be at most $$$10$$$ such queries. If your answer to the previous query was $$$0$$$, simply print $$$0$$$; otherwise, print the subset of edges for the previous query as follows: first, print the number of edges in the subset, then print the indices of the chosen edges in ascending order. The sum of indices should be equal to your answer to the previous query.
- $$$3$$$ — terminate the program.

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 one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of vertices of the tree.

Then $$$n-1$$$ lines follow. The $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \ne v_i$$$) — the endpoints of the $$$i$$$-th edge. These edges form a tree.

Then the queries follow in the format described in the statement, one line per query. There will be at least $$$2$$$ and at most $$$n+10$$$ queries. The last query (and only the last one) will be of type $$$3$$$. Note that you can read the $$$i$$$-th query only if you have already given the answer for the query $$$i-1$$$ (except for $$$i = 1$$$).

If your answer for one of the queries is incorrect and the judging program recognizes it, instead of the next query, you may receive the integer $$$0$$$ on a separate line. After receiving it, your program should terminate gracefully, and you will receive "Wrong Answer" verdict. If your program doesn't terminate, your solution may receive some other verdict, like "Time Limit Exceeded", "Idleness Limit Exceeded", etc. Note that the fact that your solution doesn't receive the integer $$$0$$$, it does not mean that all your answers are correct, some of them will be checked only after your program is terminated.

Output format:
For each query of type $$$1$$$ or $$$2$$$, print the answer on a separate line as described in the statement. Don't forget to flush the output.

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

Example input:
6
1 4
6 1
3 2
1 2
5 1
1 4
2
1 2
2
1 3
2
1 5
1 6
2
3

Example output:
1
1 1
0
0
4
2 1 3
0
0
0

Editorial:
Let's root the tree at vertex $$$1$$$ and try to analyze when a tree contains a perfect matching. If we want to find the maximum matching in a tree, we can use some greedy approaches like "take a leaf of the tree, match it with its parent and remove both vertices, repeat this process until only isolated vertices remain". If we are interested in a perfect matching, then this process should eliminate all of the vertices.
Let's modify this process a bit by always picking the deepest leaf. If there exists a perfect matching, picking the deepest leaf will ensure that the tree always remains a tree and doesn't fall apart, i. e. there will always be one connected component. It means that when we remove the leaf with its parent, this leaf is the only descendant of its parent.
It's easy to see that whenever we remove a pair of vertices in this process, for each remaining vertex, the number of its descendants is either left unchanged or decreased by $$$2$$$. It means that if a vertex has an even number of descendants, it will have an even number of descendants until it is removed, and the same for odd number of descendants.
Let's call the vertices with even number of descendants (including the vertex itself) even vertices, and all the other vertices — odd vertices. A vertex cannot change its status in the process of building the perfect matching. Each leaf is and odd vertex, and if its parent has only one child, this parent is an even vertex. So, when we remove a pair of vertices, one of them (the child) is odd, and the other of them (the parent) is even.
This leads us to another way of building the perfect matching: match each odd vertex with its parent, and make sure that everything is correct. Unfortunately, implementing it is $$$O(n)$$$ per query, so we need something faster. We can see that each even vertex has at least one odd child (because if all children of a vertex are even, then the number of its descendants, including the vertex itself is odd). In order to find a perfect matching, we have to make sure that:
• each even vertex has exactly one odd child;
• each odd vertex has an even vertex as its parent.
All this means is that the number of even vertices should be equal to the number of odd vertices: it cannot be greater since each even vertex has at least one odd child, and if it is smaller, it's impossible to match the vertices. The perfect matching itself consists of edges that connect odd vertices with their parents.
Okay, now we need some sort of data structure to maintain the status of each vertex (and the sum of edges that lead to an odd vertex if directed from top to bottom). In our problem, we have to add new leaves to the tree (it happens when a vertex is activated), and this increases the number of descendants for every vertex on the path from the root to this new leaf. So, we need some sort of data structure that supports the operations "add a new leaf" and "flip the status of all vertices on a path". One of the structures that allow this is the Link/Cut Tree, but we can use the fact that the whole tree is given in advance to build a Heavy-Light Decomposition on it, which is much easier to code. Operations on segments of paths can be done with a lazy segment tree, and each vertex then will be added in $$$O(\log^2 n)$$$.