SPOJ Brasil

Trinta e cinco anos atrás, um grupo de super heróis foi escolhido para formar a Liga da Justiça, cujo propósito era proteger a Terra dos vilões. Depois de todos esses anos protegendo a humanidade, seus membros estão se aposentando e agora é hora de escolher os novos membros da Liga da Justiça.

Para manter sua identidade secreta, digamos, secreta, super heróis normalmente usam um número inteiro para se identificar. Existem H super heróis na Terra, identificados com inteiros de 1 a H. Com uma breve olhada no jornal qualquer um consegue descobrir se dois super heróis já trabalharam juntos em uma missão. Se isso aconteceu, nós dizemos que os dois super heróis têm uma relação.

Deve haver somente uma Liga da Justiça no mundo, que poderia ser formada por qualquer número de super heróis (até mesmo um só). Também, para qualquer dois heróis na nova liga, eles têm que ter uma relação.

Também, considere o conjunto de heróis não escolhidos para fazer parte da Liga da Justiça. Para qualquer dois heróis naquele conjunto, eles não podem ter uma relação. Isso evita a criação de ligas da justiça não-oficiais. Você trabalha para uma agência encarregada de criar a nova Liga da Justiça. A agência não sabe se é possível criar a Liga com as restrições dadas, e pediu por suas habilidades de programação. Dado um conjunto de super heróis e suas relações, determine se é possível selecionar qualquer subconjunto para formar a Liga da Justiça, de acordo com as restrições dadas.

Entrada

A entrada é composta de diversos casos de teste. A primeira linha de cada caso de teste contém dois inteiros separados por um espaço, H (2 <= H <= 5x104) e R (1 <= R <= 105), indicando, respectivamente, o número de heróis e o número de relações. Cada uma das linhas seguintes contém dois inteiros separados por um espaço, A e B (1 <= A < B <= H), indicando que o super herói tem uma relação com o super herói B. Note que se A tem uma relação com B, B também tem uma relação com A. Uma relação nunca é informada duas vezes no mesmo caso de teste.

O final da entrada é dado por H = R = 0.

Saída

Para cada caso de teste na entrada imprima uma linha, contendo a letra maiúscula “Y” se é possível selecionar um subconjunto de heróis para formar a Liga da Justiça de acordo com as restrições dadas, ou a letra maiúscula “N” caso contrário.

Exemplo

Entrada
5 5
1 2
2 3
1 3
1 4
3 5
9 8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
4 3
1 2
2 3
3 4
0 0

Saída
Y
N
Y