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.