0326 - おなかペコい

時間制限 1 秒 / メモリ制限 256 MB / 得点 7 / Writer ei1333 / x 1 / 統計 /


TLE
1sec
MLE
256MB
得点
7

ストーリー

大室櫻子「おなかペコい。。。あっ!杉浦先輩のプリンが生徒会室の冷蔵庫の中にあったはず!」

プリン好きの杉浦綾乃は, プリンを取られたくない.また今日のプリンは, いつもと違ってちょっと贅沢なフルーツプリン.

追い込まれた杉浦綾乃は, しりとりを始めて プリンのことを忘れてもらうことにした.

大室櫻子「じゃあわたしから!スタンプ!」
杉浦綾乃「プリン」
大室櫻子「わ〜〜〜い!プリ〜〜ン♪」

二度とこのような失敗をしたくない杉浦綾乃を助けるために, しりとりプログラムを書いてあげよう.

問題

しりとりは, 以下にあるような一般的なルールを用いる.

  • 先頭の文字が直前の最後の文字となっている単語のみを発言できる.
  • 最後に 'n' をつく単語を言ったら負け.
  • 同じ単語を 2 回言ったら負け.

大室櫻子と杉浦綾乃は, N 個の単語のうちのいずれかを選んで, しりとりに使うことができる.それぞれの単語は, アルファベットの小文字のみで表される.しりとりは大室櫻子から始め,最初に使う単語は N 個の単語のうちどれを使ってもよい.

大室櫻子はしりとりに負けないために最善を尽くすが, しりとりに負ければプリンを忘れる.このとき櫻子に, プリンを忘れさせることができるかどうか判定せよ.

入力

N
S1
S2
:
SN

1 行目に, 使える単語の数 N が与えられる.

2 行目から N 行にかけて,使える単語 Si が与えられる.

制約

  • 2 ≤ N ≤ 20
  • 1 ≤ Si の長さ ≤ 100
  • SiSj (ij)
  • Si(1 ≤ iN) は, アルファベット小文字のみで構成される.

またジャッジデータのうちの 1 点分は以下の制約も追加で満たす.

  • N ≤ 6

出力

大室櫻子が最善を尽くしたとき, 大室櫻子が負けるようなしりとりの方法があるとき 'HAPPY', どのようにしても 大室櫻子が負けないとき 'UNHAPPY' を出力せよ.(''は出力しない.)

入出力例

入力例 1

6
bakkinbakkingamu
uma
app
umi
icmp
purin

出力例 1

UNHAPPY

大室櫻子が'bakkinbakkingamu' から始めるとする.
杉浦綾乃は, 'uma' か 'umi' を選ぶことができる.
'uma' を選ぶと, 次に櫻子は 'app' を選び, 残りは 'purin' のみとなるので綾乃が負ける.
'umi' を選ぶと, 次に櫻子は 'icmp' を選び, 残りは 'purin' のみとなるのでこちらも綾乃が負ける.
よってどのように綾乃が単語を選んでも, 櫻子が勝つので, 'UNHAPPY' を出力する.

入力例 2

4
ab
ac
ba
ca

出力例 2

HAPPY

櫻子が, 'ab' から始めるとする.
綾乃は 'ba' を選び, 櫻子は 'ac' を選び,綾乃は 'ca' を選ぶので,櫻子の負け.
櫻子が, 'ac' から始めるとする.
綾乃は 'ca' を選び,櫻子は 'ab' を選び, 綾乃は 'ba' を選ぶので,櫻子の負け.
櫻子が, 'ba' から始めるとする.
綾乃が 'ab' を選ぶと,櫻子の負け.
櫻子が, 'ca’ から始めるとする.
綾乃が 'ac' を選ぶと,櫻子の負け.
よって,櫻子がどの単語から始めても綾乃が勝つことができるので, 'HAPPY' を出力する.