Randka

Limit pamięci: 128 MB

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:

• jeżeli -ta para zakochanych przejdzie odpowiednio: on , a ona korytarzami oznaczonymi strzałkami, to spotkają się w jednej komorze jaskini,
• jest jak najmniejsze,
• w drugiej kolejności jest jak najmniejsze,
• jeżeli rozwiązanie wciąż nie jest jednoznaczne, to kobieta powinna pokonywać mniejszy dystans.

Wejście

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 .

Wyjście

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.

Przykład

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.