Shiritori(しりとり) - joi2011-day2

時間制限: 5秒

メモリ制限: 64MB

JOI 国では，100 種類の文字が使われている．これらの文字は，コンピュータ上では直接表すことが難しいので，代わりに以下の表記が用いられる．

00 01 02 03 04 05 06 07 08 09
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
30 31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 49
50 51 52 53 54 55 56 57 58 59
60 61 62 63 64 65 66 67 68 69
70 71 72 73 74 75 76 77 78 79
80 81 82 83 84 85 86 87 88 89
90 91 92 93 94 95 96 97 98 99

すなわち，数字 2 つによる 10 \times 10 通りで表される．JOI 国の辞書では，この表によって定まる文字の順番によって単語を並べている．表の上の行にある文字がより早く，同じ行の文字ではより左の文字が早い．

さて，JOI 国では今，しりとりが一大ブームである．しりとりとは，参加者が順番に，前の人が言った単語の最後の文字から始まる単語を言っていくゲームである．一度言われた単語を使うことはできない．

ある日，あなたは友達と「5 しりとり」で遊んでいた．「5 しりとり」では，通常のしりとりのルールに加え，用いる単語はすべて 5 文字でなければならない．あなたは「5 しりとり」で言われた N 個の単語のリストをコンピュータに記録していたのだが，誤って並べ替えてしまった．そこで，単語のリストから「5 しりとり」の様子を復元したい．

課題

単語のリストが与えられたとき，「5 しりとり」の様子を復元するプログラムを作成せよ．

制限

1 \leq N \leq 500\,000

単語の個数

入力

標準入力から以下の入力を読み込め.

1 行目には整数 N が書かれており，単語の個数を表す．
続く N 行には各単語が 1 行に 1 つずつ書かれている．各単語は数字ちょうど 10 個からなる文字列で表される．単語は辞書に掲載されている順に入力に書かれており，すべての単語は異なる．

出力

与えられた N 個の単語を用いた「5 しりとり」が不可能である場合，impossible と 1 行に出力せよ．

「5 しりとり」が可能である場合，用いられる N 個の単語を 1 行 1 つずつ出力せよ．可能な「5 しりとり」が複数考えられるときは，以下の条件を満たすものを選べ．

1 番目の単語が辞書に最も早く掲載されているもの
以上で定まらない場合は，2 番目の単語が辞書に最も早く掲載されているもの．
:
:
以上で定まらない場合は，N 番目の単語が辞書に最も早く掲載されているもの．

採点基準

採点用データのうち，配点の 65% 分については，現れる文字は 00 から 19 までの 20 種類に限られる．
採点用データのうち，配点の 65% 分については，N \leq 1\,000 を満たす．
採点用データのうち，配点の 40% 分については，これら 2 つの条件の両方を満たす．
採点用データのうち，配点の 90% 分については，これら 2 つの条件の少なくとも一方を満たす．

入出力の例

入力例 1	出力例 1
`5 0000010201 0102030403 0104050603 0206070801 0308090002`	`0000010201 0102030403 0308090002 0206070801 0104050603`

この例では，以下の 2 通りの「5 しりとり」が考えられる.

0000010201 → 0102030403 → 0308090002 → 0206070801 → 0104050603
0000010201 → 0104050603 → 0308090002 → 0206070801 → 0102030403

1 番目の単語は同じであり，2 番目の単語が辞書に掲載されている順番を比較して，前者を出力する.

入力例 2	出力例 2
`4 9600000098 9700000099 9800000099 9900000098`	`impossible`

この例では，可能な「5 しりとり」は存在しない．

入力例 3	出力例 3
`12 0114090401 0214051905 0304141219 0510031717 0703050011 1102190101 1108040907 1110090702 1313071203 1707120711 1902090011 1909121313`	`1909121313 1313071203 0304141219 1902090011 1108040907 0703050011 1110090702 0214051905 0510031717 1707120711 1102190101 0114090401`