En un pueblo de \(N\) personas, la persona \(i\) tiene dos contactos fijos \(X_i\) e \(Y_i\). Funciona un esquema piramidal:

• Alguien de afuera le pide \(1\) peso a una persona del pueblo (cualquiera), y esta lo paga.
• Quien paga, en algún momento posterior, les pide \(1\) peso a cada uno de sus dos contactos.
• Cada persona participa una sola vez: si ya pagó antes, ya no paga ni pide nada.

Los tiempos son arbitrarios: cualquier orden de los pedidos es posible. Una persona pierde dinero si paga y ninguno de sus dos contactos le paga (ambos ya habían participado cuando les pidió). Determina, para cada persona, si existe algún desarrollo del esquema en el que pierde dinero.

Entrada

La primera línea tiene un entero \(N\) \((3 \le N \le 1000)\).

La \(i\)-ésima de las siguientes \(N\) líneas tiene dos enteros \(X_i\) e \(Y_i\) \((1 \le X_i, Y_i \le N,\ X_i \ne i,\ Y_i \ne i,\ X_i \ne Y_i)\).

Salida

Una línea con un texto de largo \(N\) cuyo \(i\)-ésimo carácter es Y si la persona \(i\) puede perder dinero, o N si no.

Ejemplo 1

Entrada

5
2 3
3 4
4 5
5 1
1 2

Salida

YYYYY

Ejemplo 2

Entrada

4
2 3
3 4
2 4
2 3

Salida

NYYY

Regional Latinoamericana 2022 del ICPC, problema A («Asking for Money»). Versión en español redactada para este juez; el enunciado oficial, en inglés, está aquí abajo.