给定一棵由 $$$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 函数。
输入
第一行包含一个整数 $$$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$$$ 查询($$$i = 1$$$ 除外)。
如果您对其中一个查询的答案不正确并且评审程序识别出它,则您可能会在单独的行中收到整数 $$$0$$$,而不是下一个查询。收到它后,您的程序应该正常终止,并且您将收到“错误答案”的判决。如果您的程序没有终止,您的解决方案可能会收到一些其他判决,例如“超出时间限制”、“超出空闲限制”等。请注意,您的解决方案没有收到整数 $$$0$$$,这并不意味着您的所有答案都是正确的,其中一些答案只有在程序终止后才会被检查。
输出
对于 $$$1$$$ 或 $$$2$$$ 类型的每个查询,按照语句中的说明在单独的行上打印答案。不要忘记刷新输出。
示例
输入 #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