题目描述

读入一棵以 $1$ 为根的树，输出每个非根节点的父亲。

输入格式

第一行，一个整数 $n$ 表示节点数。$(1 \le n \le 100000)$ 。

之后 $n - 1$ 行每行两个正整数 $x$ 和 $y$ ，表示一条连接 $x$ 和 $y$ 的边，保证输入的图形成一棵树。

输出格式

输出 $n - 1$ 行，每行 $1$ 个整数，第 $i$ 行为节点 $i + 1$ 的父亲。

样例

6
2 1
2 3
2 4
2 5
6 5

1
2
2
2
5