MKLAR10 - Kids’ Wishes

no tags 

Kevin is a kid. He has lunch at school together with many more kids. They use to go outdoors and have lunch sitting on the ground. They love to form a big circle in which each kid has exactly two neighbors, one on the left and one on the right. Sometimes the teacher has problems arranging the circle because some kids wish to sit down next to other kids. Each kid may wish to sit down next to at most two other kids, because each kid has just two neighbors in the circle. The teacher wants to know whether it is possible to arrange the circle in such a way that all kids' wishes are satisfied. You clean up the place when the lunch ends. Since you want to finish your work as early as possible, help the teacher in answering that question.

Input

Each test case is given using several lines. The first line contains two integers K and W representing respectively the number of kids (3 ≤ K ≤ 10^9) and the number of wishes (0 ≤ W ≤ 10^5). Kids are identified with numbers between 1 and K. Each of the next W lines describes a different wish using two distinct integers A and B (1 ≤ A, B ≤ K); these values represent that kid A wishes to sit down next to kid B. Each kid has at most two wishes.

The last test case is followed by a line containing two zeros.

Output

For each test case output a single line containing an uppercase 'Y' if it is possible to arrange a circle in such a way that all kids' wishes are satisfied, or an uppercase 'N' otherwise.

Sample

input
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

output
N
Y
Y

hide comments
~: 2011-11-19 08:45:31

how any body can get ac IN TEXT !!...is judge's testcaes are known to him ...:P

Roberto: 2011-10-12 14:42:54

Why do I get TLE if in UVA Judge I get WA ¿?

Dante is not a Geek: 2011-07-04 14:10:44

SPOJ has suddenly stopped supporting C++0x? @_@

Last edit: 2011-07-05 04:45:30
Crazzyy: 2011-01-22 20:13:09

How can this be AC in text ??

PRATEEK KHURANA: 2011-01-14 13:25:01

well, my solution is just a modification of the text file in c, when i saw there are AC text solutions

Last edit: 2011-01-14 14:40:38
cjtoribio: 2010-11-10 22:46:53

THANXS for rejudge and correction i was getting TLE and ended being first. Good prob though.

Shaka Shadows: 2010-11-09 19:38:08

Test data files have been corrected and all the solutions have been rejudged. We sorry about the mistakes.

Kinan Sarmini: 2010-11-09 19:27:47

Is there anything wrong with test cases? I ran my solution on official tests, and running time is 1.5 second but I'm getting TLE :-/

.:: Pratik ::.: 2010-11-09 19:27:47

Input doesnt end with 0 0
how sad


Added by:psetter
Date:2010-11-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ACM ICPC2010 – Latin American Regional