题目描述

给定一棵 $n$ 个结点的 树，$1$ 号点为根，并规定 $1$ 号点的深度为 $1$。

假设所有结点中深度最大的结点的深度为 $mx$。

你需要求出所有深度为 $1,2,3,\cdots,mx$ 的结点的个数分别有几个。

以及顺便求出每个结点的子树大小。

$u$ 的子树指的是以 $u$ 为根的所有部分。

例如下图的树

$5$ 的子树大小指的是以 $5$ 为根的结点个数，分别是 5 3 4 一共 $3$ 个结点。

输入格式

第一行输入一个数 $n$。

接下来 $n-1$ 行每行输入两个整数 $u,v$，代表 $u,v$ 之间有一条边。

输出格式

第一行输出若干个数空格隔开，分别代表所有深度为 $1,2,\cdots,mx$ 的结点个数。其中假设 $mx$ 为深度最大的结点的深度。

第二行输出 $n$ 个空格隔开的数字分别代表结点 $1,2,\cdots,n$ 的子树大小。

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

1 3 2 1
7 1 2 1 3 2 1

数据规模与约定

对于 $100\%$ 的数据，$2 \le n \le 10^5$。