Problem D
波の王様

Picture by JD Lasica via Flickr.

あなたは、Buenos Aires Paddleboarding Competition(BAPC)の大会主催者で、 $n$ 人が参加している。大会では、最初に一人を「王」に指名して、他の人が挑戦し、勝者が次の王になる。

これを、最初の王以外の全員が$1$回ずつ挑戦するまで続ける。パドルボードの試合では、引き分けは存在しない。最後に王であった選手が大会に優勝する。 あなたは主催者として、最初の王と他の選手の挑戦する順序を決める必要がある。 ある人が不正を持ち掛け、選手の一人であるヘンクが優勝したら金を支払うと申し出た。 あなたは、特定の選手間の試合があった場合の勝敗を知っている。また、あなたは不正に手を染め、ヘンクに優勝させようとしている。どのようなスケジュールを組めばヘンクを優勝させられるだろうか。

入力

入力は以下の内容を含む。

• 先頭行は $1 \leq n \leq 1000$の整数で、選手の人数を表す。 選手には $0, \dots , n-1$ の番号が付けられ、ヘンクは$0$番となる。

• それ以降の $n$ 行にはちょうど $n$ 文字（改行を除く）が書かれる。各行は以下の書式で表される選手間の勝敗表を表す。 $i$ 行目の $j$th 番目の文字 ($0 \leq i, j < n$)は、

  • 選手 $i$ が選手 $j$ に勝つとき、’1’ となる。

  • 選手 $i$ が選手 $j$ に負けるとき、’0’ となる。

  • $i = j$ のとき、’X’となる。

出力

選手の順序を出力する。最初の選手が最初の王で、次以降の選手が順番に挑戦する。もしヘンクを優勝させることができなかったら、 “impossible”と出力する。

3
X10
0X1
10X

1 2 0

3
X10
0X0
11X

impossible