SPOJ Brasil

Kevin é uma criança. Ele almoça na escola junto com muitas outras crianças. Eles costumam ir até o pátio e almoçar sentados no chão. Eles adoram formar um grande círculo onde cada criança tem exatamente dois vizinhos, um na esquerda e outro na direita. Às vezes a professora tem problemas para organizar o círculo pois muitas crianças desejam sentar ao lado de outras crianças. Cada criança pode desejar sentar ao lado de no máximo duas outras crianças já que cada criança tem apenas dois vizinhos. A professora quer saber se é possível organizar o círculo de forma que todos os desejos de todas as crianças sejam satisfeitos. Você limpa o lugar quando o almoço termina. Já que você quer terminar seu trabalho o mais cedo possível, ajude a professora a responder essa questão.

Entrada

Cada caso de teste se estende por várias linhas. A primeira linha contém dois inteiros K e W representando respectivamente o número de crianças (3 ≤ K ≤ 10⁹) e o número de desejos (0 ≤ W ≤ 10⁵). Crianças são identificadas por números inteiros entre 1 e K. Cada uma das próximas W linhas descreve um desejo através de dois inteiros distintos A e B (1 ≤ A,B ≤ K); esses valores significam que a criança A deseja sentar ao lado da criança B. Cada criança possui no máximo dois desejos.

O último caso de teste é seguido de uma linha contendo dois zeros.

Saída

Para cada caso de teste, imprima uma única linha contendo um caractere 'Y' se é possível organizar o círculo de forma que todas crianças tenham seus desejos atendidos, ou um 'N' caso contrário.

Exemplo

Entrada:
4 3
2 3
1 3
2 1
1000000000 0
3 6
3 2
2 1
1 2
1 3
2 3
3 1
0 0

Saída:
N
Y
Y