小婷老师要帮助一只迷路的小猫回到树根。小猫所在的位置以及各节点之间的父子关系已经记录下来。

输入的第一行给出小猫当前所在节点。后面的每一行先给出一个父节点，再给出它的一个或多个直接孩子；每个非根节点恰好会出现一次作为孩子。单独一行 -1 表示所有关系输入结束。

小猫每一步只能从当前节点走到它的父节点。请输出小猫从当前位置出发，沿父节点一直走到根节点时经过的完整节点序列，包括起点和根节点。

输入格式

第一行输入一个整数 $K$，表示小猫当前所在的节点。

接下来输入若干行父子关系。每行第一个整数表示父节点，后面的所有整数表示它的直接孩子。最后输入单独一行 $-1$，表示关系输入结束。

输出格式

在一行中依次输出小猫当前位置、它的父节点、父节点的父节点，直到根节点为止。相邻编号之间用一个空格分隔。

2
1 2
-1

2 1

1
1 2
2 3
-1

1

2
1 2 3 4
-1

2 1

数据范围与约定

• 节点编号互不冲突并组成一棵树
• 小猫所在节点一定存在