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.
Bajtazar jest strażnikiem przyrody i pracuje w Jaskini Strzałkowej - znanym miejscu schadzek zakochanych par. Jaskinia ta składa się z komór połączonych jednokierunkowymi korytarzami. W każdej komorze dokładnie jeden wychodzący z niej korytarz jest oznaczony strzałką. Każdy korytarz prowadzi bezpośrednio z jednej komory do pewnej (niekoniecznie innej) komory.
Notorycznie zdarza się, że zakochane pary, które umawiają się na randki w Jaskini Strzałkowej, zapominają dokładnie ustalić miejsce spotkania i nie mogą się odnaleźć. W przeszłości prowadziło to do wielu nieporozumień i pomyłek... Od czasu, gdy w każdej komorze zainstalowano telefon alarmowy łączący z dyżurnym strażnikiem przyrody, głównym zajęciem strażników stało się pomaganie zakochanym parom w odnajdowaniu się.
Strażnicy wypracowali następującą metodę. Wiedząc, w których komorach znajdują się zakochani, mówią każdemu z nich, ile razy, odpowiednio, powinien przejść z komory do komory korytarzem oznaczonym strzałką, aby oboje mogli się spotkać. Przy tym, zakochani bardzo chcą spotkać się jak najszybciej - zależy im przecież, aby razem miło spędzać czas, a nie samotnie przemierzać korytarze. Strażnicy starają się podawać zakochanym parom takie liczby, aby ich maksima były możliwie jak najmniejsze.
Bajtazar jest już zmęczony ciągłym pomaganiem zakochanym i poprosił Cię o napisanie programu, który by to usprawnił. Program ten, na podstawie opisu Jaskini Strzałkowej oraz aktualnego położenia zakochanych par, powinien wyznaczyć par liczb i , takich że:
W pierwszym wierszu standardowego wejścia znajdują się dwie dodatnie liczby całkowite i (, ), oddzielone pojedynczym odstępem i określające liczbę komór w Jaskini Strzałkowej i liczbę zakochanych par, które chcą się odnaleźć. Komory są ponumerowane od 1 do , natomiast zakochane pary są ponumerowane od 1 do .
W drugim wierszu wejścia znajduje się liczb całkowitych dodatnich, pooddzielanych pojedynczymi odstępami: -ta liczba w tym wierszu określa numer komory, do której prowadzi korytarz oznaczony strzałką wychodzący z komory numer .
W kolejnych wierszach znajdują się kolejne zapytania zakochanych par. Każde zapytanie składa się z dwóch liczb całkowitych dodatnich oddzielonych pojedynczym odstępem - oznaczają one numery komór, w których znajduje się dana para zakochanych - najpierw on, a potem ona.
W testach wartych łącznie 40% punktów zachodzą dodatkowe warunki oraz .
Twój program powinien wypisać na standardowe wyjście dokładnie wierszy, po jednym dla każdej pary zakochanych z wejścia: -ty wiersz wyjścia powinien opisywać wynik dla -tej pary z wejścia. Każdy wiersz wyjścia powinien składać się z dwóch liczb całkowitych , , oddzielonych pojedynczym odstępem.
Dla danych wejściowych:
12 5 4 3 5 5 1 1 12 12 9 9 7 1 7 2 8 11 1 2 9 10 10 5
poprawną odpowiedzią jest:
2 3 1 2 2 2 0 1 -1 -1
Autor zadania: Alan Kutniewski.