Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

MWP4_3A - Drzewa N-arne

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 ≤ 109). 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

Dodane przez:Maciej Boniecki
Data dodania:2012-03-24
Limit czasu wykonania programu:0.100s-0.802s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:IV Mistrzostwa WWSI w Programowaniu
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.