Cło
Limit pamięci: 32 MB
Król Bajtazar postanowił uporządkować kwestie związane z
opłacaniem cła przez kupców Bajtocji.
Bajtocja składa się z miast połączonych dwukierunkowymi
drogami.
Każda droga w Bajtocji łączy dwa różne miasta.
Żadne dwa miasta nie są połączone więcej niż jedną drogą.
Drogi mogą prowadzić przez tunele i estakady.
Dotychczas każde miasto w Bajtocji pobierało cło od każdego,
kto do niego przyjeżdżał i od każdego, kto z niego wyjeżdżał.
Niezadowoleni z tej sytuacji kupcy wnieśli oficjalny protest,
w którym sprzeciwili się wielokrotnemu pobieraniu cła.
Król Bajtazar postanowił ograniczyć przywileje miast.
Wedle nowego królewskiego edyktu, każde miasto może pobierać cło
od kupców podróżujących dokładnie jedną z dróg prowadzących do niego
(bez względu na kierunek ich podróży).
Ponadto, dla każdej z dróg, podróżni podróżujący tą drogą nie mogą
być zmuszeni do płacenia cła obu miastom, które ta droga łączy.
Należy jeszcze podjąć decyzję, które miasto ma pobierać cło z
której drogi.
Rozwiązanie tego problemu król zlecił Tobie.
Zadanie
Napisz program, który:
-
wczyta ze standardowego wejścia opis układu dróg w Bajtocji,
-
dla każdego miasta wyznaczy, na której drodze dane miasto będzie
pobierać od kupców cło, lub stwierdzi, że jest to niemożliwe,
-
wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite:
i (, ),
oznaczające odpowiednio liczbę miast oraz dróg w Bajtocji.
Miasta są ponumerowane od do .
W kolejnych wierszach znajdują się opisy kolejnych dróg.
W wierszu znajdują się dwie liczby całkowite i
() oznaczające, że miasta i są
połączone bezpośrednią drogą.
Wyjście
Jeśli pobieranie cła zgodnie z wymaganiami królewskiego edyktu
nie jest możliwe, to w pierwszym i jedynym wierszu standardowego
wyjścia Twój program powinien wypisać słowo NIE.
W przeciwnym przypadku, w pierwszym wierszu Twój program powinien wypisać
słowo TAK, a w kolejnych wierszach powinny się znaleźć
informacje które miasto z jakiej drogi pobiera cło.
W wierszu powinien znaleźć się numer miasta, do którego
prowadzi droga, na której miasto nr pobiera od kupców cło.
W przypadku, gdy istnieje wiele rozwiązań, należy podać dowolne z nich.
Przykład
Dla danych wejściowych:
4 5
1 2
2 3
1 3
3 4
1 4
poprawną odpowiedzią jest:
TAK
3
3
4
1
Strzałki na rysunku wskazują miasta pobierające cło od kupców
podróżujących daną drogą.
Zwróć uwagę, że kupcy podróżujący drogą łączącą miasta 1 i 2 nie
płacą w ogóle cła.
Dla danych wejściowych:
4 3
1 3
3 4
2 3
poprawnym wynikiem jest:
NIE
Autor zadania: Michał Pilipczuk.