Perfect Matching

题意翻译

## 题目描述 给出一棵树，节点编号 $1$ 到 $n$，边编号 $1$ 到 $n-1$。最初，只有节点 $1$ 是活跃的。 你需要实现以下三种操作： - $1\ v$：激活节点 $v$ 。保证与 $v$ 直接相连的点中至少有一个是活跃的。在这之后，你需要选择一些边，使得它们端点都是活跃的，并且，每个活跃的节点在这些端点中刚好出现一次。换句话说，即选出一些边，使得它们与所有活跃的点之间有完美匹配（一个活跃的点匹配一条边，一条边匹配两个活跃的点）。然后输出所有选中的边的编号和。如果不存在这样的匹配，输出 0。 - $2$：保证此询问在某一次上一种询问之后。保证此询问不超过 10 次。如果上一个询问的结果是 0，请输出 0。否则，输出上一次询问之后所选的边的具体方案，具体的说：输出选的边的条数并从小到大输出所选边的编号。注意，本次输出的编号之和应该和你上一次输出的答案一致。 - $3$：请终止您的程序。 注意你的程序需要做到在线。这意味着你必须回答上一次询问后才能读入这一次询问，注意刷新缓冲区。 ## 输入格式 第一行一个正整数 $n(2\le n\le 2\times10^5)$。 接下来 $n-1$ 行每行两个数字 $u,v$，描述一条树上的边。按照边的编号从小到大输入。 接下来若干询问，最少 $2$ 个且最多 $n+10$ 个。 请注意如果您的程序某一次输出结果错误，下一次您将会读入 $0$，请立刻终止您的程序并得到 WA 的结果，否则可能得到一些奇怪的评测结果。 ## 输出格式 对于每一个 $1$ 或 $2$ 的询问，输出对应的答案。不要忘记输出之后刷新缓冲区。

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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

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

输出样例 #1

1
1 1
0
0
4
2 1 3
0
0
0