Problem Description

Given $ m $ strings consisting of lowercase English letters.

Determine whether there exists a rooted tree with $ m $ vertices, each corresponding to one string, such that:

• Non-leaf vertices have exactly two children.
• When vertex $ i $ is the parent of vertex $ c $, the last character of the $ i $-th string matches the first character of the $ c $-th string.

If such a tree exists, construct it.

Input Format

The input is given from the standard input in the following format:

$ N $ $ s_1 $ . . . $ s_N $

• The first line contains the number of strings $ N(1≦N≦10^4) $.
• The following $ N $ lines contain the strings. The $i+1\ (1≦i≦N)$ line contains the $ i $-th string.
• Each string has a length between 1 and 10 characters.

Output Format

Output to the standard output and ensure a newline at the end.

If no tree satisfying the conditions exists, output "NO" on the first line.

If a tree satisfying the conditions exists, the output consists of $ N+1 $ lines. The first line should contain "YES", followed by the parent index of the $ i $-th string on the $i+1\ (1≦i≦N)$ line. Output 0 if the $ i $-th string is the root.

Sample Input and Output

Sample Input #1

5
ab
bc
bd
de
df

Sample Output #1

YES
0
1
1
3
3

Sample Input #2

7
yokozuna
takayuta
namonaki
reew
semiexp
snuke
tozangezan

Sample Output #2

NO

Sample Input #3

1
i

Sample Output #3

YES
0

Notes/Hints

Partial Points

There are no partial points for this problem.

Considering the impact on the contest, 99 points for the conventional test cases and 1 point for all test cases. (16:32)

见题面 Input 部分

见题面 Output 部分