G. Layers Upon Layers
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A peculiar chef is making a cake with several layers, with each layer having a flavor. He has already baked $$$n$$$ layers, each with a flavor $$$f_i.$$$

However, the chef believes the cake tastes best if the layers are arranged in a specific way: for each pair of adjacent layers, the last letter of the lower layer's flavor must be the same as the first letter of the flavor of the layer directly above it.

For example, listing the layers from the bottom up, the order apple, eggnog, gingerbread is valid. The order apple, dominos is not valid, since e is not the same as d. The order apple, extra, apple is valid.

In addition to arranging his layers, he can also do the following to at most one layer:

  • Flip the layer, which reverses the flavor's name. So, a layer with the flavor apple flipped would have the flavor elppa.

The chef wishes to use all $$$n$$$ of his layers exactly once. Given $$$f_1, f_2, \dots, f_n$$$, find if he is able to make a valid arrangement for his cake.

Input

The first line will contain $$$n$$$ $$$(1 \leq n \leq 10^5)$$$, the number of layers the baker has.

Each of the next $$$n$$$ lines contains a string $$$f_i$$$ $$$(1 \leq |f_i| \leq 12)$$$, the flavor of the $$$i$$$-th layer, consisting only of lowercase Latin letters.

Output

If the chef cannot build a valid cake, print NO.

Otherwise, print YES followed by an integer $$$x$$$. Print $$$x=-1$$$ to flip no layer, or print the index $$$x$$$ ($$$1\le x\le n$$$) of the layer to flip.

If there are multiple valid answers, print any of them. Any $$$x$$$ is accepted as long as the chef can build a valid cake by flipping layer $$$x$$$ (or by flipping nothing, if $$$x = -1$$$).

Examples
Input
3
apple
eggnog
gingerbread
Output
YES -1
Input
3
ab
cb
cd
Output
YES 2
Input
2
cake
dough
Output
NO
Note

In the first example, no layer needs to be flipped: apple ends in e and eggnog starts with e, and eggnog ends in g and gingerbread starts with g.

In the second example, flipping layer $$$2$$$ turns cb into bc. Then ab, bc, cd is a valid cake. Without flipping, no valid cake exists.

In the third example, cake ends in e and dough ends in h, but the two flavors start with c and d. No arrangement works, even if either layer is flipped.