题目描述

给定一棵有 $n$ 个结点的二叉树，结点编号为 $1$ 到 $n$，且互不相同，根结点编号为 $1$。

请按层次遍历这棵二叉树：先输出根结点，再从左到右输出第二层的所有结点，随后从左到右输出第三层，依此类推。每一层单独占一行。

输入格式

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

接下来 $n$ 行，第 $i$ 行输入两个整数 $l_i,r_i$，分别表示结点 $i$ 的左儿子和右儿子的编号。若某个儿子不存在，对应编号为 $0$。

输出格式

输出若干行。第 $d$ 行从左到右输出深度为 $d$ 的所有结点编号，编号之间用一个空格分隔。根的深度为 $1$。

数据范围与约定

$1\le n\le 10^6$，输入保证构成一棵以结点 $1$ 为根的二叉树。

可见测试数据

输入数据 1

1
0 0

输出数据 1

1

输入数据 2

2
2 0
0 0

输出数据 2

1
2

输入数据 3

5
3 2
0 0
4 5
0 0
0 0

输出数据 3

1
3 2
4 5