思路：树形DP

定义$f[i]$表示从$i$点出发所能到达的节点数量，也就是最终输出的答案

我们首先需要去在以$i$为根的子树中找到节点编号最小的节点$u$

那么则有状态转移方程$f[i]=f[u]+1$

如果$i$是叶子结点，则$f[i]=1$

题目内容

小红最近沉迷上了PVZ，尤其喜欢自己设计一些关卡，而在设计关卡时，尤其偏爱传送门(进入门的一端后，会从另一端出现)。

这天，小红又设计了一个关卡，不同于PVZ的平面结构，这个关卡在一棵根节点为1的树上。

树上的每个节点都有一个脑子以及一个传送门，而玩家则是一个僵尸。每个传送门，会将玩家传送到该节点子树中除该节点外编号最小的节点处。

小红想知道，从任意一个节点出发，到叶节点为止，玩家一共能吃到多少脑子？

输入描述

一行一个整数$n$，表示树上的节点数量。

接下来$n-1$行，每行两个整数$u,v$，表示$u$号节点和$v$号节点之间有一条边。

$1\le n\le10^5$

$1\le u,v\le n$

输出描述

输出一行，$n$个整数。第$i$个数表示从第$i$个节点出发，可以吃到的脑子数量是多少。

样例

输入

4
1 3
3 2
4 1

输出

2 1 2 1