题目描述

给定一个有$n$个节点的树，这棵树以1号节点为根节点，请你快速计算出以每一个节点为根节点的子树所包含的节点数量。

输入描述

第一行输入一个整数$n(1 \leq n \leq 10^5)$ 表示树的节点个数。

接下来$n-1$行，每行输入两个整数$a,b(1 \leq a,b \leq n)$ ，表示$a$和$b$之间有一条边。

输出描述

输出$n$个整数，分别表示以节点$i$为根节点的子树所包含的节点数量。

样例

输入

5
1 2
2 3
2 4
1 5

输出

5 3 1 1 1

说明 如下图所示，以1号节点为根节点的子树包含：1、2、3、4、5五个节点

以2号节点为根节点的子树包含：2、3、4三个节点。以此内类推