该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

一颗包含 $N \ (1 \le N \le 10^6)$ 个顶点无根树（编号为 $1$ ~ $N$），每次操作如下：

找到树中编号最小且度数为1的节点（叶子）$x$，把与 $x$ 相连的节点 $y$ 加入序列，并将该叶子节点 $x$ 及 $x$ 与 $y$ 之间的边删除。

执行以上操作 $N−2$ 次，最终得到的长度为 $N - 2$ 的整数序列就是这棵树的 Prufer 编码。

显然：再执行一次，得到的数一定是 $N$。

你的任务是：根据给定的 Prufer 编码，重建这棵树的邻接表表示。

输入格式

输入是一组代表 Prufer 编码的整数，整数之间用空格或换行符分隔。

输出格式

输出每个顶点的邻接列表。格式要求如下：

• 每行输出一个顶点；
• 格式为：顶点编号 : 后跟其邻接顶点编号，用空格分隔；
• 所有邻接列表应按照顶点编号升序排列；
• 每个邻接列表内部的顶点也应按升序排列。

示例

输入

2 1 6 2

输出

1: 4 6
2: 3 5 6
3: 2
4: 1
5: 2
6: 1 2