Hamiltonian Circuit

A directed graph $G$ has $N$ vertices and $N(N-1)/2$ edges. The vertices are numbered 0 to $N-1$. For two distinct vertices $i$ and $j$, exactly one of the edge from $i$ to $j$ and the edge from $j$ to $i$ is present, so $G$ is a complete graph once you ignore the directions.

$X$ is the adjacency matrix of $G$. $X_{i,j}$ is + when the edge from $i$ to $j$ is present and - when it is not. $X_{i,i}$ is always ..

A Hamiltonian circuit of $G$ is a cycle of length $N$ that passes through every vertex of $G$ once. Given $G$, decide whether a Hamiltonian circuit exists, and print one if it does.

The first line has the number of vertices $N$. Each of the next $N$ lines has one row of the adjacency matrix $X$. The $j$-th character of the $i$-th of those lines is $X_{i,j}$.

If $G$ has no Hamiltonian circuit, print -1.

Otherwise print the $N$ vertices of a Hamiltonian circuit in the order they are passed, separated by one space. A graph can have several Hamiltonian circuits, so print exactly the one that the procedure below builds.

Keep a sequence $c_0, c_1, \dots, c_{k-1}$ of distinct vertices. The sequence stands for the cycle $c_0 \to c_1 \to \dots \to c_{k-1} \to c_0$, and every neighbouring pair, including the pair $(c_{k-1}, c_0)$, is an edge of $G$. Start from the sequence that holds vertex 0 alone and repeat the following until the sequence holds all $N$ vertices. A vertex outside the sequence is called free.

1. If a free vertex $v$ has both an edge from a sequence vertex to $v$ and an edge from $v$ to a sequence vertex, take the smallest such $v$. Find the smallest index $i$ with $X_{c_i,v}$ equal to + and $X_{v,c_{(i+1) \bmod k}}$ equal to +, then put $v$ directly after $c_i$. Such an index $i$ always exists.
2. Otherwise, collect the pairs $(w, u)$ of free vertices where every sequence vertex has an edge to $w$, $u$ has an edge to every sequence vertex, and the edge from $w$ to $u$ is present. Take the smallest such pair in lexicographic order and append $w$ and then $u$ to the end of the sequence.

When $G$ has a Hamiltonian circuit, one of the two rules applies at every turn, and vertex 0 stays in front of the sequence, so the printed circuit starts at vertex 0.

• $3 \le N \le 1\,000$