输出每个节点的子树大小

题目描述

输入一棵无向树，以 1 号节点为根。对每个节点 i，输出以 i 为根的子树中共有多少个节点。

输入格式

第一行一个整数 n。接下来 n-1 行，每行两个整数 u,v。

输出格式

输出 n 个整数，依次为 siz[1],siz[2],...,siz[n]。

样例

输入样例 1

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

输出样例 1

8 4 3 1 2 1 1 1

数据范围与提示

1≤n≤100000。