FRAKTAL - konkurs programistyczny

Zapewne znasz grę w trzy kubki.

Na stole znajduje się pewien przedmiot, np. moneta. Prowadzący grę zakrywa ją kubkiem, obok którego stawia kolejne dwa kubki. Wiedząc, gdzie znajduje się przedmiot, gracz może wejść do gry, o ile uiści stosowną opłatę. Jeżeli wygra, odzyska postawione pieniądze, a także wygra jakąś nagrodę. Przegrana oznacza utratę pieniędzy na rzecz prowadzącego. Sama gra sprowadza się do wskazania przez gracza kubka, pod którym znajduje się przedmiot. Sęk w tym, że przed udzieleniem odpowiedzi, prowadzący grę przestawia kubki w zawrotnym tempie, a śledzenie jego ruchów wymaga koncentracji i dobrej pamięci.

Powyższy opis dotyczy uczciwej gry w trzy kubki. Cała "zabawa" polega jednak na tym, że na ogół prowadzący nie jest uczciwy i w pewnym momencie wykonuje takie ruchy kubkami, że może łatwo i niepostrzeżenie dla gracza przenieść monetę (lub inny przedmiot) z jednego kubka do drugiego, a nawet w ogóle usunąć ją z gry.

Bitomir trafił na Bajtockie zawody gry w n kubków. Amatorzy faktycznie koncentrują się na n = 3, ale Bitomir jest profesjonalistą i preferuje gry z wykorzystaniem tysięcy kubków. Chcąc wykryć nieuczciwych prowadzących potrzebuje programu, który zasymuluje przebieg rozgrywki.

Wejście

Na wejściu, w pierwszej linii, podana będzie całkowita liczba dodatnia n (2 < n < 10⁵) oznaczająca liczbę kubków w grze. Pozycje kubków, od lewej do prawej, opisane są kolejnymi liczbami naturalnymi od 1 do n. Kubkom, od lewej do prawej, przypisujemy również unikatowe ID będące liczbą równą pierwotnej pozycji kubka.

W kolejnej linii wejścia podana będzie całkowita liczba dodatnia q (n < 10⁵) oznaczająca liczbę zmian kolejności kubków w grze. Dalej, w kolejnych q liniach, podane będą zawsze dwie liczby całkowite dodatnie i oraz j (i, j ≤ n) oznaczające, że w danym momencie należy zamienić miejscami kubki znajdujące się na pozycjach i oraz j. Dopuszczamy przypadki, kiedy i = j.

Wyjście

Na wyjściu należy wypisać, zaczynając od lewej, ID każdego kubka po wykonaniu wszystkich q zamian.

Przykład

5
4
1 2
2 3
5 4
2 2

2 3 1 5 4