AlgoLiga 2018

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≤10⁵) i p - numer ulicy, przy której znajduje się poczta (1≤p≤n).

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