問題
今、巷でMCY-GAMEというゲームがナウでヤングな人たちの間で爆発的に大流行しています。
名前の通りMagentaとCyanとYellowの3色だけで構成されているシンプルなゲームです。
ゲームのルールとしては、最初にM,C,Yの3色が完全にランダムに光ります。
その中で隣り合っている色違いの2つのボタンを同時に押すと、押された2つのボタンはどちらの色でもなかった色に変化します。
隣り合っている色違いの2つのボタンのペアが複数ある場合は、どのペアから押してもかまいません。
すべてのボタンの色が1色になったときゲームクリアとなります。
すべてのボタンの色を1色にするまでの最短手数とクリアにかかった手数の差を最短手数から引いたものが得点として加算されます。
ボタンの色の変化のパターンを2手まですべて書いたものが上の図です。
このとき隣り合った色違いのボタンのペアは3組あるので、
1手目では中段に並べて書いた3通りの色のどれかに変わります。
1手目で中段左側2つのように変わったとき、2手目ですべてのボタンをYellowにすることができます。
それに対して、1手目で中段の1番右のように変わったときには、
2手目ではどのパターンでもすべてのボタンを同じ色にすることができません。
トップランカーを目指す友人君の練習用として、MCYだけで構成されるランダムな文字列から、
1色になるまでの最短手数を求めるプログラムを書くことにしました。
ただし、MCYの列を与えるのはゲームではなく友人君であるため、何手かかっても1色にならない場合も存在してきます。
そういう場合には「最短手数」ではなく「NA」を出力するような仕様にしたいと思います。
また、文字列は2以上10以下のM,C,Yからなる文字列で与えられるものとします。
入力
1行目 ボタンの色の情報(半角文字列)
複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。各データセットは以下の通りです。
出力
1行目 すべてのボタンの色が同じになるまでに要する最短手数(整数)またはNA
入力データセット毎に以下の形式で出力します。
入出力例
入力例
MCYMY MCCYCCM CYM CYMCMYCM CYYMYCYMM YCMYYMCYYM MMMMM CYCM 0
出力例
5 7 1 6 NA 8 0 4