Spedycja
Limit pamięci: 128 MB
Bajtazar i Bitocy pracują w firmie spedycyjnej „Jak nie dziś, to jutro”.
Dostali właśnie bardzo odpowiedzialne zadanie, polegające na przewiezieniu
paczek z magazynów rozmieszczonych w różnych miastach Bajtocji do
centralnego magazynu w stolicy.
W Bajtocji jest miast ponumerowanych liczbami od 1 do ; stolica jest
miastem o numerze 1. Miasta są połączone dwukierunkowymi drogami; z każdego
miasta da się dojechać do każdego innego.
Nasi bohaterowie postanowili urozmaicić sobie pracę i zagrać w następującą grę.
Wykonują oni na przemian ruchy.
Ruch polega na pojechaniu samochodem dostawczym
do wybranego miasta, zabraniu z tamtejszego magazynu dowolnej niezerowej liczby paczek
i przewiezieniu ich do miasta położonego o jedną drogę bliżej od stolicy.
Ustalili, że wygrywa ten, kto jako pierwszy nie będzie miał już żadnej paczki
do przewiezienia – może on wtedy pójść do szefa i zgarnąć premię za wykonaną pracę.
Zakładając, że obaj grają optymalnie i Bajtazar wykonuje pierwszy ruch, wyznacz, który z nich wygra.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita ()
oznaczająca liczbę miast w Bajtocji.
W -tym z kolejnych wierszy znajdują się po dwie liczby całkowite ,
(, )
oznaczające numery miast, które łączy -ta droga.
W -tym z kolejnych wierszy znajduje się po jednej liczbie całkowitej
(), która oznacza liczbę paczek w magazynie miasta
o numerze .
Wyjście
Na wyjściu należy wypisać jedno słowo TAK, jeśli wygra Bajtazar, lub
NIE w przeciwnym wypadku.
Przykład
Dla danych wejściowych:
5
1 3
2 1
1 4
4 5
1
2
1
1
poprawną odpowiedzią jest:
TAK
Autor zadania: Tomasz Idziaszek.