Problem Description

You are given a directed graph with $n$ vertices. Between any two vertices, there is exactly one directed edge.

For each vertex $v$, find a simple path starting from $v$ that visits the maximum number of vertices, and does not visit any vertex twice or more.

Input Format

The first line contains a positive integer $n$, the number of vertices.

The next $n-1$ lines follow. The $i$-th of these lines contains $i-1$ numbers.

If the $j$-th number is $1$, it means there is a directed edge $j\rightarrow i+1$. If it is $0$, it means there is a directed edge $j\leftarrow i+1$.

Output Format

Output $n$ lines. On the $i$-th line, first output a positive integer $k$, the number of vertices on an optimal path starting from vertex $i$.

Then output $k$ positive integers, in order, representing each vertex on the path.

If there are multiple optimal solutions, output any one.

This problem uses SPJ (made by Claris).

4
1
1 1
1 0 1

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

Hint

For $100\%$ of the testdata, $2\le n\le 2 \times 10^3$.

Translated by ChatGPT 5