CF1633F 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$ 的询问,输出对应的答案。不要忘记输出之后刷新缓冲区。