Nasty Boys

Time Limit : 1 sec, Memory Limit : 65536 KB

Problem A: Nasty Boys

Problem

太郎君は学校のロッカーに大事な本を隠しているので他の人よりとても厳重に管理していて、学校で支給された鍵に加えて以下のようなボタン認証式の鍵を設置しています。

ただパスワードを忘れやすい太郎くんはパスワードを一筆書きで書けるものにしてしまう癖があります。更に詰めの甘い太郎君は自分のパスワードを考えるときに候補を紙に書いていました。その紙をたまたま拾ったは次郎君は、性格が悪いので捨てずにロッカーを開けることに挑戦しました。

しかし紙にはなんと1000個ものパスワードの案が書かれており、全ての入力を試すと日が暮れてしまいそうです。 そこで太郎君の癖を知っている次郎君は、調べる回数を減らすために1000個のパスワードの中から一筆書きできるものだけを取り上げることにして、その作業をプログラマーの貴方に頼むことにしました。

1つのデータセットにつき必ず候補は一つ以上存在します。一筆書きのルールを以下に示します。

  1. 同じ文字は連続しない。例えばAAAは許されない。
  2. 上下左右4方向に一筆書きが可能。斜め方向に移動しない。
  3. ボタン配列の枠外に出て連続することはない。例えばABCAのような移動は許されない。
  4. 一度通った文字の上も何度も通過可能。
  5. ボタン1文字のみの入力も一筆書きとみなす。

Input

入力は以下のように1000個の文字列群からなり、各行はAからIまでの1文字以上10文字以下の大文字のアルファベット列である。それぞれ文字列のデータの重複はないものとする。

string1
string2
...
string1000

Output

入力のうち候補となるパスワード(candidatePassword)のみ抜き出して以下のように列挙せよ。なお以下の場合はN個の候補が挙げられている。

candidatePassword1
candidatePassword2
...
candidatePasswordN

出力は入力の文字列の順と同じであり順番を入れ替えてはならない。

Sample Input

ABCFI
ABCABCABC
AEI
EFC
(中略)
DEHED
EEEEE
(以上でちょうど1000個)

Sample Output

ABCFI
EFC
(中略)
DEHED

Source: University of Aizu Programming Contest 2013 , Aizu Commpetitive Programming Camp 2013 Day 2, Japan, 2013-09-04