描述

有$N$个节点，给出每个节点的父节点编号（ 节点编号为1,2,3,..., N ），求输出树的前序遍历。

输入输出格式

输入

第一行为一个正整数 $N$， 表示一共有多少个节点。

第二行为一个正整数 $root$，表示根节点的编号。

随后$N$行，每行为两个整数，分别表示该节点的左右子节点编号。特别地，当子节点为空时，子节点编号为-1。

输出

一行，$N$个正整数，为树的前序遍历的节点编号。

例子

3
1
2 3
-1 -1
-1 -1

1 2 3

样例1说明

根据输入数据，树的形状如图，前序遍历的结果为1 2 3

4
2
-1 -1
1 3
-1 4
-1 -1

2 1 3 4