B - コメント Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

ニワンゴ君は、動画サイトのコメントの表示方法の新たな案を考えています。

コメントは画面の右から左に 1 秒につき 1 文字分の速さで流していきます。コメントが N 個ある動画では、それらのコメントを好きな順番で 1 秒おきに流していきます。つまり、i 個目に流したコメントは、最初に流したコメントから右に i-1 文字ずれた位置に表示されることになります。

ニワンゴ君は「N 個のコメントの同じ位置の文字が全て同じ文字である状況」を 1 回以上作りたいと思っているのですが、コメントを流す順番をうまく決めることによって作ることができるでしょうか？「N 個のコメントの同じ位置の文字が全て同じ文字である状況」とは、全ての i について i 個目に流したコメントの X-i 文字目の文字が Y である、というような整数 X と文字 Y の組が存在する状況を表します。

入力

入力は以下の形式で標準入力から与えられる。

N
S_1
S_2
:
S_N
  • 1 行目には、コメントの個数を表す 1 つの整数 N (2 ≦ N ≦ 200) が空白区切りで与えられる。
  • 2 行目からの N 行には、コメントの情報が与えられる。このうち i 行目には、1 つの文字列 S_i が与えられる。S_i は小文字アルファベット (a-z) のみからなる長さが 1 以上の文字列であり、i 番目のコメントを表す。また、コメントの文字列の長さの和は 10^5 以下である。

部分点

この問題には部分点が設定されている。

  • N ≦ 52 かつ、コメントの文字列の長さの和が 2,525 以下であるデータセット 1 に正解した場合は、30 点が与えられる。
  • 全てのテストケースに正解した場合は、上記とは別に 60 点が与えられる。

出力

コメントを流す順番をうまく決めることによって「N 個のコメントの同じ位置の文字が全て同じ文字である状況」を 1 回以上作ることができる場合は YES、作ることができない場合は NO を 1 行に出力せよ。出力の末尾に改行を入れること。

入力例1

3
abcd
bdac
aca

出力例1

YES

2 番のコメント、1 番のコメント、3 番のコメントという順番でコメントを流した場合、

bdac
 abcd
  aca

のように表示され、左から 4 文字目の位置の文字が全て c になります。

入力例2

4
dwango
niconico
niwango
ginza

出力例2

NO