King of the Waves

You run a king of the hill tournament with $n$ participants, the Buenos Aires Paddleboarding Competition (BAPC). One participant starts as king and the others challenge the king one at a time. The winner of a match becomes the new king. Every participant except the starting one challenges exactly once, and a paddleboarding match never ends in a draw. Whoever is king after the last match wins the tournament.

You are the organiser, so you pick who starts as king and the order of the challenges. Someone offers you a large sum of money if participant $0$, Henk, wins the tournament. You happen to know, for any two participants $x$ and $y$, which of them would win their match. So you decide to rig the game. Decide whether a schedule that makes Henk win exists, and if it does, print the schedule defined in the output section.

The first line contains an integer $n$ ($1 \le n \le 1000$), the number of participants. The participants are numbered $0$ to $n-1$, and Henk is participant $0$.

Each of the next $n$ lines contains exactly $n$ characters. The $j$-th character of the $i$-th line describes the match between participant $i$ and participant $j$ ($0 \le i, j < n$):

• 1 if participant $i$ beats participant $j$,
• 0 if participant $i$ loses to participant $j$,
• X if $i = j$.

If no schedule makes Henk win, print impossible.

Otherwise print the single schedule defined by the rule below.

Build a tree rooted at participant $0$ with a breadth first search. Mark participant $0$ as visited and put it in a queue. While the queue is not empty, take the participant $u$ at the front of the queue and look at $j = 0, 1, \dots, n-1$ in increasing order. Whenever $j$ is not visited yet and $u$ beats $j$, mark $j$ as visited, record $u$ as the parent of $j$, and push $j$ to the back of the queue. A schedule that makes Henk win exists if and only if this search visits every participant.

Traverse that tree in preorder, visiting a participant before its children and visiting the children of a participant in increasing order of index. Print the traversal reversed on one line, with the numbers separated by single spaces. The participant printed first starts as king, and the others challenge the king in the printed order.

Whenever some schedule makes Henk win, this schedule makes him win too. Other winning schedules can exist, and only this one is accepted.