Archiwum zadań programistycznych WWSI

W ogródku Warszawskiej Wyższej Szkoły Informatyki rośnie wiele niezwykłych gatunków drzew - w tym drzewa N-arne. Jest to bardzo rzadki gatunek, obiekt westchnień wszystkich dendrologów. Jego unikatowość wynika ze sposobu w jaki powstają nowe drzewa. Drzewo N-arne owocuje wyłącznie raz przez całe swoje życie, a z każdego owocu wyrasta dokładnie N nowych drzew. Nic więc dziwnego, że drzewo o wartości N=2 jest niesłychanie rzadkie, wyhodowanie kilkudziesięciu osobników może zająć dziesiątki, a nawet setki lat!

Niestety wśród drzew porastających ogródek naszej uczelni rozprzestrzeniła się bardzo dziwna choroba. Niektóre z drzew zaczęły gubić igły, a ich kora usycha... Ściągnięci dendrolodzy orzekli, że choroba ta jest prawdopodobnie genetyczna i aby znaleźć środek zapobiegający usychaniu drzew trzeba zbadać drzewo od którego wszystko się zaczęło. Jest to niezwykle trudne ponieważ nie wszystkie drzewa chorują, zdarza się, że przez szereg pokoleń choroba zanika po czym ujawnia się znowu. Pomóc może zidentyfikowanie pierwszego wspólnego przodka dla m badanych przez specjalistów drzew. Z taką właśnie prośbą dendrolodzy zwrócili się do Ciebie - napisz program, który pomoże ocalić te niezwykle rzadkie rośliny. Zawsze poszukujemy wspólnego przodka, co oznacza że nie może być nim żadne z badanych drzew. Nie zaistnieje również sytuacja, w której choruje pierwsze zasadzone w ogródku drzewo.

Wejście

W pierwszej linii wejścia znajduje się dokładnie jedna liczba całkowita Z (1 ≤ Z ≤ 31) określająca liczbę zestawów danych.

Pierwszą linię każdego zestawu danych stanowi liczba N (2 ≤ N ≤ 1000) określająca ilu potomków ma badany gatunek drzewa. W drugiej linii zestawu znajduje się liczba M (2 ≤ M ≤ 800000) opisująca liczbę badanych drzew. W kolejnych M liniach znajdują się opisy miejsc badanych drzew jakie zajmują w strukturze ogrodu. Każdy opis składa się z dwóch liczb i, j (2 ≤ i ≤ 30; 1 ≤ j ≤ 10⁹). Liczba i określa, do którego pokolenia dane drzewo należy, a liczba j to numer porządkowy wśród drzew z i-tego pokolenia. Dla N=2 pierwsze drzewo z danego pokolenia będzie miało potomków 1 i 2, drzewo drugie 3 i 4 itd.

Wyjście

Dla każdego zestawu danych należy wypisać w osobnej linii dwie liczby, i oraz j określające pierwszego wspólnego przodka M badanych drzew.

Przykład

Wejście:

2
4
3
4 15
4 16
2 2
3
4
5 30
5 28
4 10
4 11

Wyjście:

1 1
3 4