Vasúti sínek

Andy imádja a fából készült vonat- és sínpályakészletét. Az apukájának mindennap új pályát kell számára építenie. Andy azokat a pályákat szereti a legjobban, amelyek egy kört alkotnak, azaz amelyekben nincs elágazás vagy zsákutca. Így órákig vonatozhat körbe-körbe, amíg be nem következik a nagy bumm, ami romba dönti az egész építményt.

A kérdés a következő: Adott sínpályaelemekből lehet-e kört építeni az összes elem felhasználásával?

A pályaelemeket a két végükön található csatlakozókkal adjuk meg. A szabványos elemek egy „apa” és egy „anya” csatlakozóval rendelkeznek, léteznek azonban nem szabványos elemek is, amelyeken két apa, illetve két anya csatlakozó található, ahogy az alábbi kép jobb alsó sarkában is látható:

Az illeszkedéshez minden apa csatlakozónak egy anyához kell kapcsolódnia. Eltérően az igazi fából készült pályáktól, a mi elemeink flexibilisek, így a hosszuk és az alakjuk most nem számít. Ugyanannak az elemnek a két vége azonban nem illeszthető össze egymással.

A bemenet specifikációja

A bemenet a tesztesetek számával kezdődik. A következő sorok egy-egy tesztesetet írnak le, amelyek egy legalább 1, legfeljebb 50 pályaelemet leíró listából állnak. Minden elemet két betűvel reprezentálunk: M jelenti az apa, F pedig az anya csatlakozót. Az elemek egymástól egy-egy szóközzel vannak elválasztva. A kör építésénél az elemeken található csatlakozókat csak a bemeneten megadott sorrendben szabad figyelembe venni, tehát az elemeket nem szabad megfordítani!

A kimenet specifikációja

Minden tesztesetre egy sort kell a kimenetre írni, amely a LOOP vagy a NO LOOP szöveggel jelzi, hogy lehetséges-e az összes elemből egyetlen kört építeni vagy sem.

Példa bemenet

1. 4
2. MF MF
3. FM FF MF MM
4. MM FF
5. MF MF MF MF FF

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. LOOP
2. LOOP
3. LOOP
4. NO LOOP

letöltés szöveges állományként