In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
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.