P3561 [POI 2017] Tourist

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.

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 $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).**

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