問題文

半角英小文字からなる文字列が$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