题目描述

给定一个 $N$ 个点的树，你需要在 $N$ 个点中选择一个点作为起点，接下来每一步，你可以选择一条与当前点相邻的边，并移动到这条边的另一个端点。

现在小 $L$ 想要知道，移动 $i$ 次最多可以经过多少不同的节点。一个节点可以多次经过，多次经过的节点只算一次。

你需要对每个 $i\ (1\le i\le 2\times N)$ 求出答案。

输入格式

第一行两个正整数 $N$ 分别表示节点数。

接下来 $N - 1$ 行，每行两个正整数 $u,v$ 表示节点 $u,v$ 之间存在一条无向边。

输出格式

输出一行 $2\times N$ 个整数，第 $i$ 数表示移动 $i$ 次的答案。

样例 #1

样例输入 #1

3
1 2
1 3

样例输出 #1

2 3 3 3 3 3

提示

数据范围与约定

对于 $10\%$ 的数据，保证 $N\le 10$。

对于 $30\%$ 的数据，保证 $N\le 10^2$。

另有 $60\%$ 的数据，保证 $N\le 10^3$。

对于 $100 \%$ 的数据，保证 $1\le N\le 5\times 10^5$