#131. 树的广度优先遍历

树的广度优先遍历

题目描述

给定一棵拥有 nn 个节点的树(结点编号 1n1\sim n),结点 1 为根节点,遍历树,按照广度优先遍历的先后顺序输出节点编号。

输入格式

第 1 行一个整数 nn,表示树中节点的数量。接下来若干行,每行两个整数 x,yx, y,表示 xxyy 的父节点。

输出格式

输出一行,按照广度优先遍历的先后顺序输出节点编号,在遍历一个节点的所有子结点时, 按输入的先后顺序遍历。输出的编号之间用空格分隔。

样例

输入#1

9
1 3
1 2
1 4
2 7
3 6
3 5
4 8
4 9

输出#1

1 3 2 4 6 5 7 8 9

数据范围

对于 100% 的测试数据满足:1n1001≤n≤100