二叉树的位置映射

难度：T2

【知识点：树表示与遍历】

前置知识：二叉树、编号数组、孩子兄弟和递归遍历。

题目描述

给出非空二叉树的普通身份编号与左右孩子关系。规定根布局位置1，位置p的左孩子位置2p，右孩子位置2p+1。求每个普通身份编号对应的布局位置。

输入格式

第一行n r；随后n行，第i行左孩子编号和右孩子编号。保证全部结点恰好构成题意所述合法树。

输出格式

一行n个整数，按普通身份1..n顺序输出位置。

样例输入

4 1
2 3
0 4
0 0
0 0

样例输出

1 2 3 5

样例解释

根1位置1，结点2位置2，结点3位置3，结点4是2的右孩子，位置5。

数据范围

1≤n≤20。普通结点编号在1..n，空孩子/兄弟记0。