B - しりとり木

Time Limit: 1 sec / Memory Limit: 256 MB

問題文

半角英小文字からなる文字列がm個与えられる。

文字列1つにつき1つ、計m個の頂点からなる根付き木であって、

  • 葉以外の頂点はちょうど2つの子を持つ
  • 頂点iが頂点cの親のとき、 i 番目の文字列の最後の文字が c 番目の文字列の最初の文字に一致する

が成立するような木が存在するか判定せよ。

存在するときは構成せよ

13:35 問題文の誤字を修正

申し訳ありませんが、B問題のテストケースに間違いがあったため、テストケースを16:30より追加します。(16:10)


入力

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

 N 
 s_1 
.
.
.
 s_N 
  • 一行目には文字列の数 N(1≦N≦10^4) が与えられる。
  • 続く N 行には、文字列が与えられる。 i+1 (1≦i≦N) 行目にはi 番目の文字列が与えられる。
  • それぞれの文字列の長さは1文字以上10文字以下である。

部分点

この問題に部分点は存在しない。

コンテストへの影響を鑑みて、従来のテストケースに99点、全てのテストケースに1点とします。(16:32)

出力

出力は標準出力に行い、末尾に改行を入れること。

条件を満たす木が存在しない場合、1行目に"NO"と出力する。

条件を満たす木が存在する場合、出力はN+1 行からなる。 1行目に"YES"と出力し、その後 i+1 (1≦i≦N) 行目にi番目の文字列の親の番号を出力する。もしi番目の文字列が根なら0を出力する。


入力例1

5
ab
bc
bd
de
df

出力例1

YES
0
1
1
3
3

入力例2

7
yokozuna
takayuta
namonaki
reew
semiexp
snuke
tozangezan

出力例2

NO

入力例3

1
i

出力例3

YES
0