Laiko ribojimas: 0.5s

Atminties ribojimas: 32MB

Duomenų failas: mario.in

Rezultatų failas: mario.out

Jei norite pateikti savo sprendimą - prisijunkite.

Mario

Drąsiajam Mario ir vėl teks gelbėti princesę! Norint tą padaryti jam teks pereiti sudėtingą vamzdyną - iš vamzdžių padarytą labirintą.

Mario pradeda savo kelionę pirmajame kambaryje, turėdamas 100 gyvybės žiedų (pavogtų iš Sonic'o). Iš šio kambario vienakrypčiais vamzdžiais jis gali nukeliauti į kitus kambarius. Šiuose kambariuose jis gali rasti iki 100 (įskaitant) gyvybės žiedų arba priešų, atimančių iš Mario iki 100 žiedų. Išėjus iš kambario tiek priešai, tiek žiedai atsinaujina, tad vėl patekus į tą patį kambarį Mario galės atsinaujinti arba prarasti savo žiedus.

Pamatęs kokį sudėtingą vamzdyną teks pereiti, jam pasidarė įdomu ar pasiekti princesę išvis įmanoma.

Pradiniai duomenys

Įvestį sudaro iki 20 testų.

Testai pradedami skaičiumi 2\\leqN\\leq100, nurodančiu kambarių kiekį (speciali reikšmė -1 žymi testų pabaigą). Sekančiose N eilučių pateikiami kambarių aprašai. i'toji eilutė pradedama skaičiumi -100\\leql\\leq100, kuris nusako kiek gyvybių Mario gaus patekęs į kambarį. Tada seka skaičius 0\\leqe<100 - kambarių, pasiekiamų iš i'tojo, kiekis. Galiausiai pateikiami vamzdžiais pasiekiamų, kambarių numeriai n_1,n_2,\\ldots,n_e (n_j\\not=i). Po šių aprašų seka kitas testas.

Mario visada pradeda savo kelionę pirmajame kambaryje, o princesė visada jo laukia N'tąjame kambaryje (šiuose kambariuose Mario nei gauna, nei praranda gyvybių).

Išvestis

Kiekvienam testui, atskirose eilutėse, reikia atspausdinti žodį NE, jei princesės pasiekti nepavyks. Tačiau, jei Mario sugebės nenumiręs nukeliauti iki princesės, reikia išvesti žodį TAIP.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
4
0 1 2
5 1 3
8 1 4
0 0
5
0 2 2 3
-100 1 4
10 1 2
-1 1 5
0 0
-1
 
TAIP
TAIP