Crachás reversíveis

Time limit: 3000 msMemory limit: 256 MB

Há $n$ crachás numerados de $1$ a $n$ . Cada crachá tem uma letra minúscula na frente e outra no verso; as letras podem ser iguais.

Você pode escolher a face visível de cada crachá e colocar todos eles em uma fila, em qualquer ordem. Construa uma fila cujas letras visíveis formem um palíndromo, isto é, uma sequência igual quando lida da esquerda para a direita ou da direita para a esquerda. Cada crachá deve ser usado exatamente uma vez.

Input

A primeira linha contém $n$ ( $1 \le n \le 200\,000$ ). Cada uma das próximas $n$ linhas contém duas letras minúsculas de a a z: a letra da frente e a do verso do crachá $i$ .

Output

Se for impossível, imprima NAO. Caso contrário, imprima SIM na primeira linha e, na segunda, $n$ inteiros não nulos. O valor $i$ significa usar a frente do crachá $i$ ; o valor $-i$ significa usar seu verso. Os inteiros indicam a ordem da fila. Qualquer solução válida será aceita.

Samples

Sample 1

Input

3
a b
b c
a c

Output

SIM
2 3 -1

As frentes, nessa ordem, formam aba.

Sample 2

Input

2
a a
b b

Output

NAO

Não há como formar um palíndromo com uma letra a e uma letra b.