题目描述

题目译自 XXIV Olimpiada Informatyczna — I etap Turysta

字节城曾经是个美丽、交通便利的国家，每座城市之间都有双向直达道路。可惜，比特城发动战争，用「比特城极化磁铁」把所有道路变成了单向。战争虽已结束，但磁铁的影响让字节城的交通陷入混乱。

著名旅行家朗金特先生战前计划游遍字节城所有城市。现在这可能行不通，他只能尽量多逛几座城。请你写个程序，为他从每座可能的起点城市规划一条路线，尽可能多地游览不同城市，且每座城只经过一次。假设朗金特先生可在任意城市结束旅程。

输入格式

输入第一行是一个整数 $n$ $(2 \leq n \leq 2000)$，表示字节城的城市数量，城市编号从 $1$ 到 $n$。

接下来的 $n-1$ 行描述当前道路状况。第 $i$ 行描述编号为 $i+1$ 的城市与之前所有城市的连接，包含 $i$ 个数字（$0$ 或 $1$）。若第 $j$ 个数是 $1$，则道路从 $j$ 号城市通向 $i+1$ 号城市；若为 $0$，则方向相反，从 $i+1$ 到 $j$。

输出格式

输出 $n$ 行，第 $i$ 行描述从 $i$ 号城市出发、访问最多不同城市（每城仅一次）的路线。

每行开头是一个整数 $d \geq 1$，表示路线上的城市数，后面跟 $d$ 个整数，表示朗金特先生依次访问的城市编号。若有多条最长路线，输出任意一条即可。

样例

输入

4
1
1 1
1 0 1

输出

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

附加样例

• $n=3$，形成环路；
• $n=2000$，每条路都指向编号较小的城市。

数据范围与提示

详细子任务附加限制及分值如下表所示。