Byteotia 曾经是一片极其美丽的土地，交通也非常便利——每一对城镇之间都曾有直接的双向道路相连。然而，Bitotia 向 Bytoetia 宣战，并启动了“极化咬合磁铁”（Biting Magnet of Polarization, BMP）。结果，所有的道路都变成了单向的。尽管冲突早已成为过去，但道路的极化和随之而来的交通混乱却一直持续至今。

在战争之前，著名的游客 Longint 先生曾计划游览 Byteotia 的所有城镇。如今，这样的游览可能已经无法实现，因此 Longint 先生可能被迫满足于尽可能多地访问城镇。请编写一个程序，确定从 Byteotia 的每个城镇出发的最长游览路线，使得该路线在不重复访问任何城镇的前提下，访问尽可能多的城镇。Longint 先生可以在任何城镇开始他的游览，也可以在任何城镇结束。

输入格式

标准输入的第一行包含一个整数 $n$ ($2 \le n \le 2000$)，表示 Byteotia 的城镇数量。城镇编号为 $1$ 到 $n$。接下来有 $n-1$ 行，描述了 Byteotia 道路系统的当前状态。第 $i$ 行描述了编号为 $i+1$ 的城镇与编号较小的城镇之间的直接道路；该描述包含 $i$ 个数字，每个数字要么是 $0$ 要么是 $1$：如果该行中的第 $j$ 个数字为 $1$，则表示城镇 $j$ 与城镇 $i+1$ 之间的道路当前方向为从 $j$ 指向 $i+1$。如果该数字为 $0$，则表示道路当前方向为从 $i+1$ 指向 $j$。

输出格式

程序应向标准输出打印 $n$ 行，第 $i$ 行应描述从城镇 $i$ 出发且在不重复访问任何城镇的前提下访问城镇数量最多的路线。该描述应以一个整数 $d \ge 1$ 开头，表示路径上的城镇数量，随后是 $d$ 个整数，表示 Longint 先生依次访问的城镇编号；描述中的所有数字均应以单个空格分隔。如果从某个城镇出发存在多条最长路线，则可以打印其中任意一条。

样例

样例输入 1

4
1
1 1
1 0 1

样例输出 1

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

子任务

测试集由以下子任务组成。在每个子任务内，可能包含多个测试组。