Ở ngôi trường nhỏ của Kevin, mỗi dịp đầu tháng đều có một buổi tiệc đặc biệt dành cho học sinh. Trong buổi tiệc, tất cả lũ trẻ được xếp ngồi quanh một chiếc bàn tròn khổng lồ để cùng nhau ăn uống, trò chuyện và vui chơi.

Có tất cả ~K~ đứa trẻ, được đánh số từ ~1~ đến ~K~. Chúng ngồi thành một vòng tròn kín, và vì ngồi vòng tròn nên:

• Mỗi đứa trẻ sẽ có chính xác ~2~ người bạn ngồi cạnh - một bạn bên trái, một bạn bên phải.
• Không có đứa trẻ nào ngồi "một mình" hoặc có quá nhiều bạn bên cạnh.

Nghe thì tưởng đơn giản, nhưng thật ra việc sắp xếp lại không hề dễ dàng. Lũ trẻ trong trường vốn rất… "khó tính": nhiều đứa đặt ra những mong muốn đặc biệt. Chẳng hạn, có đứa nói rằng: "Tớ muốn ngồi cạnh cậu ~A~!" hoặc: "Tớ chỉ thấy vui nếu có cậu ~B~ ngồi sát bên tớ!".

Mỗi mong muốn như vậy được mô tả bởi một cặp số ~(A, B)~, nghĩa là đứa trẻ ~A~ muốn ngồi cạnh đứa trẻ ~B~. Trong vòng tròn, mong muốn này có thể được thỏa mãn nếu ~A~ ngồi bên trái ~B~, hoặc ~A~ ngồi bên phải ~B~ - miễn sao chúng ở cạnh nhau.

Tuy nhiên, để thỏa mãn tất cả các mong muốn cùng lúc, liệu có cách xếp chỗ nào hợp lý hay không? Đó là câu hỏi khiến các thầy cô đau đầu, và họ cần bạn - một chuyên gia toán - lập trình – giải quyết.

Nhiệm vụ: Với mỗi buổi tiệc, hãy xác định xem có thể sắp xếp tất cả ~K~ đứa trẻ quanh vòng tròn để mọi mong muốn đều được thỏa mãn hay không?

• Nếu có thể, in ra Y.
• Nếu không thể, in ra N.

Input

• Dữ liệu gồm nhiều test và kết thúc bằng một dòng chứa 0 0.
  • Dòng đầu tiên của mỗi test chứa hai số nguyên ~K~ và ~M~ với:
    • ~K~ - số đứa trẻ ~(3 \le K \le 10^9)~.
    • ~M~ - số mong muốn ~(0 \le M \le 10^5)~.
  • ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~A~ và ~B~ ~(A, B \le K)~, mô tả rằng đứa trẻ ~A~ muốn ngồi cạnh đứa trẻ ~B~.

Output

• Với mỗi test (ngoại trừ dòng 0 0), in ra một dòng duy nhất:
  • Y nếu có thể sắp xếp thoả mãn mọi mong muốn.
  • N nếu không thể.

Sample Input

4 3
2 3
1 3
2 1
3 6
3 2
2 1
1 2
1 3
2 3
3 1
1 3
2 1
1000000000 0
0 0

Sample Output

N
Y
Y