题目描述

给定一颗树，包含 $n$ 个结点，结点编号从 $1 \sim n$，接下来会有 $n-1$ 条边，每条边包含两个整数 $l，r$，表示结点 $l$ 与结点 $r$ 相连。

请你输出 $n$ 行，第 $i$ 行输出与第 $i$ 个结点直接相连的结点，输出时按升序顺序输出，同时在最后输出一行，表示拥有最多结点数量相连的结点编号，如果有并列的，则输出编号最小的一个。

输入格式

• 第一行输入一个整数 $n$ 代表结点个数。
• 接下来 $n-1$ 行，每行两个整数，代表相连的两个结点。

输出格式

输出 $n$ 行，第 $i$ 行输出与第 $i$ 个结点直接相连的结点，输出时按升序顺序输出。

最后第 $n+1$ 行，输出拥有最多结点数量的结点编号，如果有并列的，则输出编号最小的一个。

样例

6
1 2
1 3
1 4
3 5
4 6

2 3 4
1
1 5
1 6
3
4
1

提示

样例1解释

在第一个样例中，与 $1$ 相连的结点个数有 $3$ 个，所以最后一行输出 $1$。

数据范围

对于所有测试数据，保证：$1 \leq n \leq 10^5$。