ghemotoace

Alexa cumpărat pentru pisica sa $n$ ghemotoace de culori diferite. În fiecare zi $i$ din următoarele $t$, pisica va alege $q_i$ perechi de ghemotoace adiacente cu care să se joace, și va interschimba pozițiile ghemotoacelor din fiecare pereche. Alex, știe culorile ghemotoacelor care au fost interschimbate, dar nu și ordinea în care s-au realizat interschimbările. Astfel el vă cere să găsiți ordinea în care se află ghemotoacele în fiecare zi.

Culorile sunt codificate prin numere naturale de la $1$ la $n$. Inițial, ghemotoacele sunt sortate crescător
după acest indice al culorii.
Răspunsul pentru fiecare zi va fi dat sub forma unui cod reținut într-o variabilă de tip unsigned long
long și obținut din următoarea formulă: ($\sum_{i=0}^{n-1} 23^{n-1-i} \ \cdot \ v_i$) modulo $2^{64}$, unde $v_i$ înseamnă culoarea ghemotocului de pe poziția $i$.

Protocol de interacțiune

Concurentul va implementa funcția init, cu următoarea semnătura:

void init (int n, int nrTestCase);

Prin intermediul acestei funcții vei primi numărul $n$ și numărul testului actual.

De asemenea, concurentul va implementa și funcția makeSwaps, cu următoarea semnătura.

unsigned long long makeSwaps (int q, int a[], int b[]);

Paramtetrii acestei funcții au următorul sens:

• $q$ este numărul de perechi de ghemotoace care sunt interschimbate
• $a$ și $b$ doi vectori de $q$ elemente care descriu perechile de culori care trebuie interschimbate. Perechea $i$ (cu $i$ de la $0$ la $q - 1$) este ($a[i]$, $b[i]$). Se garantează că $a[i] \neq b[i]$. Ordinea celor două numere în cadrul perechii este aleatoare. Perechile acestea sunt date într-o ordine nu neapărat identică cu cea în care au fost realizate interschimbările de către pisică.

Funcția va întoarce rezultatul cerut în problemă. Concurentul trebuie să nu implementeze funcția main.

Restricții și precizări

• Funcția init va fi apelată o singură dată la începutul programului.
• A se observa că numărul $t$ nu este dat ca parametru în funcția init. El rămâne necunoscut programului concurenților. Cu toate acestea, el se află în fișierul de intrare.
• Funcția makeSwaps va fi apelată de $t$ ori, iar în cadrul unui apel al acestei funcții orice pereche (neordonată) de culori apare cel mult o singură dată.
• Punctarea se va face separat, testele fiind independente unul de altul
• Primul test ($nrTestCase = 1$) are proprietatea că perechile sunt date în ordinea în care s-au efectuat interschimbările. Acest test valorează $7$ puncte.
• Următoarele $2$ teste respectă următoarele restricții: $2 \leq n \leq 20 \ 000$ și $t = 1$. Aceste teste valoreaza câte $12$ puncte.
• Următoarele $3$ teste respectă următoarele restricții: $2 \leq n, t, q_i \leq 50$. Aceste teste valorează $11$ puncte.
• Următoarele $4$ teste respectă următoarele restricții: $2 \leq n, t, q_i \leq 20 \ 000$ Aceste teste valorează $9$ puncte.
• $\sum_{i = 1}^{t} q_i \leq 1 \ 000 \ 000$ pentru toate testele.

Exemplul 1

ghemotoace.in

4 2 -1
2
1 2
1 3
4
4 3
2 4
3 2
1 4

ghemotoace.out

25948
50302

Explicație

$N = 4$

$t = 2$

$nrTestCase = -1$ (acest test nu se află printre cele folosite la evaluare)

Pentru prima zi:

$[1, 2, 3, 4] \rightarrow [2, 1, 3, 4] \rightarrow [2, 3, 1, 4]$

Observați că secvența $[1, 2, 3, 4] \rightarrow [3, 1, 2, 4] \rightarrow [3, 2, 4, 1]$ este greșită deoarece elementele $1$ și $3$ nu sunt adiacente când sunt interschimbate.

$25948 = 23^2 \cdot 3 + 23^2 \cdot 3 + 23^1 \cdot 1 + 23^0 \cdot 4$

Pentru a doua zi:

$[2, 3, 1, 4] \rightarrow [2, 3, 4, 1] \rightarrow [2, 4, 3, 1] \rightarrow [4, 2, 3, 1] \rightarrow [4, 3, 2, 1]$

$50302 = 23^3 \cdot 4 + 23^2 \cdot 3 + 23^1 \cdot 2 + 23^0 \cdot 1$