你的任务是编写一个程序，该程序可以以两种方式使用：作为编码器和作为解码器。

编码器会得到一棵含有 $n$ 个节点的树，并需要将树中的所有节点全部移除。在每一步中，编码器可以移除当前树中的任意一个叶子节点。

解码器会得到一个列表，其中包含编码器依次移除的节点之间的距离，解码器需要据此重建树的原始结构。

解码器需要构建出与原树结构相同的任意一棵树（更准确地说，它必须与原树同构）。

输入格式

第一行包含一个整数 $t$，其值为 1（编码器）或 2（解码器）。

第二行包含一个整数 $n$：树中的节点数。节点编号为 $1,2,\dots,n$。

如果 $t=1$，接下来有 $n-1$ 行描述这棵树。每行包含两个整数 $a$ 和 $b$，表示节点 $a$ 和 $b$ 之间有一条边。

如果 $t=2$，则只有一行，包含 $n-1$ 个整数：依次被移除的节点之间的距离。

输出格式

如果 $t=1$，编码器必须输出一个数字 $1,2,\dots,n$ 的排列：节点从树中被移除的顺序。

如果 $t=2$，解码器必须输出 $n-1$ 行来描述树的结构。

样例

输入 1

1
3
1 2
2 3

输出 1

1 3 2

输入 2

2
3
2 1

输出 2

2 3
1 3

子任务

子任务 1 (21 分)

$2 \le n \le 10$

子任务 2 (47 分)

$2 \le n \le 500$

子任务 3 (32 分)

$2 \le n \le 10^5$