Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|
Problem hidden

LISTFRAN - Listonosz Franek

Listonosz Franek, rozwożąc listy i inne przesyłki, codziennie pokonuje rowerem wiele kilometrów ulicami swojego rewiru. Denerwuje go to, że czasami musi przejeżdżać dwa razy jakąś ulicę lub jej fragment. Od dawna próbuje więc opracować najkrótszą możliwą trasę, czyli taką, której długość będzie równa sumie długości wszystkich ulic w rewirze. Dodatkowym warunkiem jest to, aby trasa rozpoczynała się i kończyła w tym samym miejscu - na poczcie, w której Franek pracuje.

Franek, na własny użytek, ponumerował kolejnymi liczbami naturalnymi (zaczynając od 1) wszystkie punkty, w których jakaś ulica zbiega się z inną lub się kończy (ślepa uliczka). Następnie opisał każdą ulicę dwiema liczbami oznaczającymi punkty: początkowy i końcowy. 

Napisz program, który sprawdzi, czy możliwa jest do wyznaczenia taka trasa, jakiej poszukuje Franek. Warto wiedzieć, że wszystkie ulice w rewirze Franka są dwukierunkowe, oraz że nie ma takiej ulicy, do której nie można byłoby dojechać. Występują też ulice w kształcie pętli, czyli takie, które kończą się tam gdzie się zaczynają.

Wejście

W pierwszej linii znajdują się dwie liczby naturalne: n - liczba ulic w rewirze Franka (1≤n≤105) i p - numer ulicy, przy której znajduje się poczta (1≤pn).

W każdej z następnych n linii znajduje się opis kolejnych ulic w postaci dwóch liczb naturalnych a i b, oznaczających odpowiednio punkty, w których dana ulica zaczyna się i kończy.

Wyjście

Jedno słowo "TAK", jeśli jest możliwe wytyczenie poszukiwanej przez Franka trasy, lub "NIE" w przeciwnym wypadku.

Przykład 1

Wejście:
3 1
1 2
2 3
3 1
Wyjście:
TAK

Przykład 2

Wejście:
4 4
1 2
2 3
3 1
2 4
Wyjście:
NIE

Dodane przez:Witold Długosz
Data dodania:2011-11-17
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.