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.|

FR_19_03 - Trzy Kubki

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 < 105) 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 < 105) 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

Wejście:

5
4
1 2
2 3
5 4
2 2

Wyjście: 

2 3 1 5 4

Dodane przez:anonimowy
Data dodania:2024-03-05
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM32-GCC COBOL D-CLANG D-DMD ELIXIR FANTOM GOSU GRV JS-MONKEY NIM OBJC OBJC-CLANG PICO RUST SCM qobi CHICKEN VB.NET

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.