CF1633F.Perfect Matching

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.

你将得到一棵包含 $n$ 个顶点（编号为 $1$ 到 $n$）和 $n-1$ 条边（编号为 $1$ 到 $n-1$）的树。初始时，除顶点 $1$ 外，其余所有顶点均处于非激活状态。

你需要处理三种类型的查询：

• $1$ $v$ — 激活顶点 $v$。保证在执行该查询前，顶点 $v$ 处于非激活状态，且其至少有一个邻接顶点是已激活的。激活顶点后，你必须选择树中的一组边，使得每个已激活的顶点恰好与其中一条被选中的边关联，而每个非激活的顶点不与任何被选中的边关联——即该边集需构成树中已激活顶点子图的一个完美匹配。若存在这样的边集，则输出其中所有边的编号之和；否则输出 $0$。
• $2$ — 此类查询仅在类型 $1$ 的查询之后立即出现，且至多出现 $10$ 次。若你对上一个查询的回答是 $0$，则直接输出 $0$；否则，按如下方式输出上一个查询所对应的边集：首先输出该边集中边的数量，然后按升序输出所有被选中边的编号。这些编号之和应等于你对上一个查询的回答。
• $3$ — 终止程序。

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

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.

第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）——树的顶点数。

接下来是 $n-1$ 行。第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$；$u_i \ne v_i$）——第 $i$ 条边的两个端点。这些边构成一棵树。

随后是若干查询，格式如题目描述中所述，每个查询占一行。查询总数至少为 $2$，至多为 $n+10$。最后一个查询（且仅最后一个查询）的类型为 $3$。注意：你只能在已对第 $i-1$ 个查询（$i = 1$ 时除外）给出答案后，才能读入第 $i$ 个查询。

若你对某个查询的回答错误，且评测程序识别出该错误，则你将不会收到下一个查询，而是在单独一行收到整数 $0$。收到该整数后，你的程序应正常终止，此时你会得到 “Wrong Answer”（答案错误）的评测结果。若你的程序未终止，则可能得到其他评测结果，例如 “Time Limit Exceeded”（时间超限）、“Idleness Limit Exceeded”（空闲超限）等。请注意：你的程序未收到整数 $0$ 并不意味着所有回答均正确；部分回答仅在你的程序终止后才会被检查。

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.

对于每个类型为 $1$ 或 $2$ 的查询，按题目描述在单独一行输出答案。别忘了刷新输出。