题目描述

给定一棵 $n$ 个节点的无根树，节点编号为 $1 \sim n$。对于每个节点 $i$，计算其作为根节点时，整棵树的子树大小（即该节点作为根时，其管辖的所有节点数量，包括自身）。

输入格式

第一行包含两个整数 $n$ 和 $rt$（$1 \leq n \leq 10^5$，$1 \leq rt \leq n$），其中 $rt$ 为任意指定的根节点（仅用于构建树结构，不影响最终计算）。
接下来的 $n-1$ 行，每行包含两个整数 $a$ 和 $b$（$1 \leq a, b \leq n$），表示节点 $a$ 和节点 $b$ 之间有一条无向边。

输出格式

按节点编号从小到大的顺序，输出 $n$ 个整数，每个整数表示对应节点作为根时的子树大小，相邻整数之间用空格分隔。

样例

样例输入

6 1  
1 2  
5 2  
2 3  
4 2  
5 6  

样例输出

6 5 1 1 2 1  

样例解析

• 当节点 $1$ 作为根时，子树包含所有 $6$ 个节点。
• 当节点 $2$ 作为根时，其父节点为 $1$，子树包含节点 $2,3,4,5,6$，共 $5$ 个节点。
• 当节点 $3$ 作为根时，其父节点为 $2$，子树仅包含自身，共 $1$ 个节点。
• 其他节点同理，子树大小由其作为根时的层级结构决定。

数据范围与提示

• 数据范围：
  • 30% 的数据：$n \leq 100$
  • 60% 的数据：$n \leq 1000$
  • 100% 的数据：$n \leq 10^5$