Longest Simple Path in a Tournament Graph

Given a tournament graph with \(n\) vertices, where between any two distinct vertices there is exactly one directed edge, find for each vertex \(v\) a simple path (no vertex is visited more than once) starting from \(v\) that visits the maximum number of vertices. In other words, for every vertex \(v\) you should output a path starting at \(v\) with maximum length among all simple paths starting at \(v\).

A tournament graph satisfies that for any two different vertices \(u\) and \(v\), exactly one of the edges \(u \to v\) or \(v \to u\) exists. Note that a simple path is a path which does not include any vertex more than once.

Example: Consider \(n=3\) with edges defined as follows in a transitive tournament: \[ \begin{array}{ccc} 0 & 1 & 1\\ 0 & 0 & 1\\ 0 & 0 & 0 \end{array} \] For vertex 1, one longest path is 1 \(\to\) 2 \(\to\) 3, for vertex 2 it is 2 \(\to\) 3, and for vertex 3 it is simply 3.

inputFormat

The input begins with an integer \(n\) (the number of vertices). Following that are \(n\) lines, each containing a string of length \(n\). The \(j\)-th character on the \(i\)-th line is either '1' or '0'. For \(i \neq j\), if the character is '1', it indicates that there is an edge from vertex \(i\) to vertex \(j\); otherwise (i.e. if it is '0'), the edge is directed from vertex \(j\) to vertex \(i\). The diagonal characters can be arbitrary (but will not affect the answer).

Note: Vertices are numbered from 1 to \(n\) for the output.

outputFormat

For each vertex \(v\) from 1 to \(n\), output a line. The line should begin with an integer \(k\) indicating the number of vertices in the longest simple path starting from \(v\), followed by \(k\) space-separated integers that denote the sequence of vertices (in order) in that path. (The vertices in the output should be 1-indexed.)

sample

3
011
001
000

3 1 2 3
2 2 3
1 3