子树重心

给出一棵有根树，求出每棵子树的重心。

输入

第一行，$n, r$，表示树的结点数和根，接下来的 $n-1$ 行，每行两个数 $u, v$，表示两结点之间有无向边连接。 $2\leq n\leq 10^5$ 。

输出

$n$ 行， 第 $i$ 行表示以 $i$ 为根的子树的重心编号（如果有多个，请输出深度较小的那个）。

样例

3 1
1 2
1 3

1 
2
3

Limitation

1s, 1024KiB for each test case.