24098번 - しりとり (Shiritori) 다국어

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

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

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

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

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

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

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

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

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

• 1 ≤ N ≤ 500 000 単語の個数