MKLAR10 - Kids’ Wishes

no tags 





English Vietnamese





Gene and Gina have a particular kind of farm. Instead of growing animals and vegetables, as
it is usually the case in regular farms, they grow strings. A string is a sequence of characters.
Strings have the particularity that, as they grow, they add characters to the left and/or to the
right of themselves, but they never lose characters, nor insert new characters in the middle.
Gene and Gina have a collection of photos of some strings at different times during their growth.
The problem is that the collection is not annotated, so they forgot to which string each photo
belongs to. They want to put together a wall to illustrate strings growing procedures, but they
need your help to find an appropriate sequence of photos.
Each photo illustrates a string. The sequence of photos must be such that if si comes imme-
diately before si+1 in the sequence, then si+1 is a string that may have grown from si (i.e., si
appears as a consecutive substring of si+1). Also, they do not want to use repeated pictures,
so all strings in the sequence must be different.
Given a set of strings representing all available photos, your job is to calculate the size of the
largest sequence they can produce following the guidelines above.



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.






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.






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.






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





hide comments
: 2012-09-04 01:36:51

My solution is running correct on the official testcases is there anything special about output?

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

how any body can get ac IN TEXT !! 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:~!(*(@*!@^&
Time limit:0.132s-0.661s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ACM ICPC2010 – Latin American Regional