C. LCT
time limit per test
3 с
memory limit per test
1024 megabytes
input
standard input
output
standard output

给定一棵包含 $$$ n $$$ 个节点的以 $$$1$$$ 为根的树，节点从 $$$1$$$ 到 $$$ n $$$ 编号， 边按照输入顺序从 $$$1$$$ 到 $$$n - 1$$$ 编号。树的每条边一开始都处于"连上"状态。你需要支持以下操作：

对于给定的两个整数 $$$ x $$$ 和 $$$ y $$$，首先切换编号为 $$$ x $$$ 的边的状态，如果它原本是"断开"状态，则将其切换为"连上"状态；如果它原本是"连上"状态，则将其切换为"断开"状态。然后查询在只考虑所有当前"连上"状态下的边的情况下，与节点 $$$ y $$$ 位于同一个连通块中的根节点的编号是多少？根节点定义为连通块中深度最小的节点。

你需要处理共 $$$ q $$$ 次这样的操作，并在每次操作后输出查询结果。

Input
  • 第一行包含两个整数 $$$ n, q $$$，分别表示树的节点数和询问个数。
  • 接下来 $$$ n-1 $$$ 行，每行包含两个整数 $$$ u $$$ 和 $$$ v $$$，表示树中的一条边连接了节点 $$$ u $$$ 和 $$$ v $$$。每条边都有唯一的编号，从 $$$1$$$ 到 $$$ n-1 $$$，按输入的顺序编号。
  • 接下来 $$$ q $$$ 行，每行包含两个整数 $$$ x $$$ 和 $$$ y $$$，表示对于边 $$$ x $$$ 进行切换状态操作，然后查询节点 $$$ y $$$ 所在连通块的根节点。
Output

对于每次操作，在切换边 $$$ x $$$ 的状态后，输出节点 $$$ y $$$ 所在连通块的根节点。

Examples
Input
5 5
2 1
3 2
4 3
5 4
3 3
1 2
4 4
2 5
1 3
Output
1
2
4
5
3
Input
5 6
2 1
3 2
4 1
5 1
3 2
3 3
4 4
3 2
1 5
1 2
Output
1
1
1
1
5
1
Note

$$$2 \leq n \leq 10^6$$$

$$$1 \leq q \leq 5\times 10^5, 1 \leq u, v \leq n, 1 \leq x \leq n - 1, 1 \leq y \leq n$$$

所有输入保证形成一棵树。