题目描述

按照之字形顺序从上向下打印二叉树。

即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

输入

第一行一个整数n，表示二叉树有$n$个节点。

接下来$n-1$行，每行2个整数分别表示父节点和子节点，如果当前父节点已有左儿子则当前子节点是右儿子

输出

从上到下按层打印二叉树，同一层的结点按从左到右的顺序打印，每一层打印到一行。

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

1 
4 2 
3 5 
6 11 7 
8 9 
10

提示

$1<n<=10000$

节点编号从$1$到$n$且$1$一定是根节点