もんだいー
みちゅいさんはしりとりが好きな誇り高きシリトラーである。
みちゅいさんはしりとりにおいては勇者である。
みちゅいさんはしりとりで負けられない。
みちゅいさんがしりとりで負けると、畑が荒らされ、金を奪われ、けーたろー村の民は夜枕を濡らして悲しむ。
しかし！みちゅいさんが勝った日には、狂喜乱舞の祭りが行われ、村人に美酒が振る舞われる。
みちゅいさんはなんとしてでもけーたろー村に襲いくるシリトラーを倒さねばならない。
けーたろー村の神殿には、みちゅいさんお手製の「しりとり単語記録器」がある。
この機械は、みちゅいさんの行ったしりとりの内容をその都度記録するスグレモノである。
こものさんは先日みちゅいさんに頼まれ、みちゅいさんのその日の戦績をまとめることとなった。
−−−−−−−−しかし、みちゅいさんの作った「しりとり単語記録器」に致命的な欠陥が見つかった。
「一戦ごとのすべての単語」の情報は記録されているものの、肝心の「誰が何の単語を発したか」とか「どちらが先攻、後攻だったか」といった情報がまるっきり記録されていなかったことが判明した。
これでは本当の勝敗などわかりっこないので、こものさんはとりあえず記録されている単語を使ってしりとりが最後まで続けば「みちゅいさんの勝ち」とした。
実際にみちゅいさんが勝ったか負けたかはどうでもいいのでとりあえず勝利の美酒を飲みたいこものさん(クズ)はなんとかしてみちゅいさんを勝利にさせることにした。
今からあなたが書くのは、そんな薄汚れた欲にまみれた話の一ページ...
※ここでいうしりとりは、単語をローマ字表記した文字列で行う。
(例)「komono」 → 「osaka」 → 「asobu」
入力
N s1 s2 : sN
1 行目に整数 N が与えられる。
Nは文字列 s の個数を表している。
2 行目からは文字列 si が与えられる。
これは、そのしりとりで使われた単語を表している。単語は必ず偶数個与えられる。
出力
全ての単語を使用して、しりとりが最後までできるようであれば「MITSUWIN」を、できないようであれば「NAKISOU」を出力せよ。
制約
全ての入出力ケースについて以下を満たす。
- 0 ≦ N ≦ 10, 0 ≦ 文字列の長さ ≦ 20
- 同じ単語は入力として与えられない。
- 大文字は入力として与えられない。(テストケースには影響しません。)
入出力例
入力例1
4 komono asobu osaka umasou
出力例1
MITSUWIN
解説
記録されている単語は「komono」「osaka」「asobu」「umasou」の4つである。
「komono」 → 「osaka」 → 「asobu」 → 「umasou」と場が展開していった場合、みちゅいさんの勝ちとなる。
入力例2
4 adoria awwwwa anthia ketaro
出力例2
NAKISOU
解説
しりとりが全ての単語を使って最後まで続かないのでなきそうである。