9495 - 节点的信息

给定一个树,每个节点用1~n编号。求每个节点所在子树的节点数,及每个节点的深度

输入

输入第一行两个数n和r,r表示树的根。

接着n-1行,每行2个数字a,b。表示a和b之间有一条边。

输出

输出第2行,每行n个数,用空格分割。

第一行输出1~n节点深度

第二行输出1~n节点子树数量

样例

输入

8 1
1 2
2 3
3 4
4 5
4 6 
2 7
7 8

输出

1 2 3 4 5 5 3 4
8 7 4 3 1 1 2 1

提示

n \leq 10^5

来源

原创

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题