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.