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.