Fişierul intrare/ieşire:	ghemotoace.in, ghemotoace.out	Sursă	InfoPro, Etapa 3, Grupa B
Autor	Alexandru Petrescu	Adăugată de	Mihai-Cristian Popescu •mihai50000
Timp execuţie pe test	0.115 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Ghemotoace

Alex a cumpărat pentru pisica sa n ghemotoace de culori diferite pe care le sortează după culoare. În următoarele t zile pisica va alege q perechi de ghemotoace adiacente cu care să se joace şi va interschimba poziţiile gheotoacelor din fiecare pereche. Alex ştie culorile ghemotoacelor care au fost interschimbate dar nu şi ordinea acestora. 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.
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ă:  ( v[i] = culoarea ghemotocului de pe poziţia i )

Date de intrare

Fişierul de intrare gheomotoace.in conţine pe prima linie numerele n şi t. Pe următoarele linii se află descrierea fiecărui test astfel: pe următoarea linie se găseşte q_i urmat de q_i linii care conţin câte două numere ce descriu culorile ghemotoacelor care sunt interschimbate.

Date de ieşire

În fişierul de ieşire gheomotoace.out se vor afla t numere, câte unul pe fiecare linie. Pe linia i se va gasi răspunsul pentru ziua i.

Restricţii

• Orice pereche de culori apare o singură dată în fişierul de intrare.
• Pentru 10 puncte: perechile de culori sunt date în ordinea în care s-au realizat interschimbările.
• Pentru alte 40 puncte: 1 ≤ n, t, q_i ≤ 100
• Pentru alte 50 puncte: 1 ≤ n, t ≤ 100.000 şi 1 ≤ q_i ≤ 1.000.000

Exemplu

Explicaţie

[1, 2, 3] -> [2, 1, 3] -> [2, 3, 1]
1228 = 23² * 2 + 23¹ * 3 + 23⁰ * 1

Cum se trimit solutii?