Šeštadieninė informatikos olimpiadininkų mokykla

Duota krūvelė domino kauliukų. Kiekvienas domino kauliukas perskirtas į dvi puses. Kiekvienoje pusėje užrašytas skaičius iš intervalo 0..6. Du kauliukus galima sujungti, jei skaičiai, užrašyti ant sujungiamų kauliukų pusių, sutampa.

Užduotis

Reikia nustatyti, ar krūvelėje esančius kauliukus galima išdėlioti į vieną liniją.

Laikykite, kad krūvelė nėra tuščia ir kauliukų skaičius neviršija 20 000.

Pradiniai duomenys

Pradiniais duomenimis nurodyta, kiek kokių kauliukų yra krūvelėje. Kiekvienoje eilutėje yra trys skaičiai: pirmieji du apibūdina kauliuką, trečiasis parodo, kiek tokių kauliukų yra krūvelėje, pavyzdžiui:

5 6 8

Tai reiškia, kad krūvelėje yra 8 kauliukai su skaičiais 5 ir 6.

Iš viso pradinių duomenų byloje yra ne daugiau kaip 28 užpildytos eilutės, nes tiek yra skirtingų kauliukų.

Rezultatai

Rezultatas – žodis GALIMA arba NEGALIMA.

Pavyzdžiai

0 1  1
1 2  2
2 3  2

GALIMA