W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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.
Napisz program, który:
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ą.
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.
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.