== include(page="template/taskheader" task_id="minmaxstore") ==
Poveste şi cerinţă...
Popel si Popita au un vector $V$ cu $N$ elemente distincte. Popel vrea sa determine elementul minim si Popita elementul maxim din acest vector. Acestia primesc o serie de operatii de tipul $STORE(A, B)$ care pun in pozitia A minimul si in B maximul dintre cele $2$ valori. Mai exact, $V[A] = min(V[A], V[B])$ si $V[B] = max(V[A], V[B])$. La sfarsit, cei $2$ dau $2$ pozitii reprezentand pozitia la care se afla elementul minim, respectiv elementul maxim. Cand Comisarul a venit sa verifice daca Popel si Popita isi fac treaba cum trebuie, acestia observa ca au pierdut vectorul initial si nu au cum sa ii arate Comisarului daca au dat pozitiile de mimim si maxim corecte. Singura lor scapare este daca cele $2$ pozitii sunt valide pentru orice permutare de lungime $V$. Mai exact, pentru orice permutare $P$ de lungime $N$, daca aplicam operatiile de STORE date, elementul minim si maxim se pozitioneaza pe cele $2$ pozitii date de personajele noastre.
h2. Date de intrare
Fişierul de intrare $minmaxstore.in$ ...
Fişierul de intrare $minmaxstore.in$ va contine pe prima linie un numar natural $T$, numarul de teste. Pentru fiecare test, prima linie va contine $2$ numere naturale $N$ si $M$, lungimea vectorului si numarul de operatii STORE. Urmatoarele $M$ linii contin cate $2$ numere naturale $A$ si $B$ reprezentand cate o operatie de tipul STORE. Ultima linie contine alte $2$ numere $PMIN$ si $PMAX$, pozitia minimului si a maximului.
h2. Date de ieşire
În fişierul de ieşire $minmaxstore.out$ ...
Fişierul de ieşire $minmaxstore.out$ va contine $T$ linii, pe linia $i$ aflandu-se raspunsul pentru testul $i$:
* Daca doar Popel a dat un raspuns valid, raspunsul este $"Popel"$
* Daca doar Popita a nimerit, raspunsul este $"Popita"$
* Daca amandoi au dat un raspuns corect, afisati $"Popeala"$
* Daca niciunul nu a nimerit, afisati $"Comisarul"$
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ Suma M-urilor dintr-un fisier va fi ≤ 1.000.000$
* $1 ≤ N ≤ 100.000$
* $1 ≤ M ≤ 200.000$
h2. Exemplu
table(example). |_. minmaxstore.in |_. minmaxstore.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|4
4 5
1 2
1 3
1 4
2 4
3 4
1 4
3 2
1 2
1 3
1 3
3 3
1 2
1 3
2 3
2 3
2 1
2 1
1 2
| Popeala
Popel
Popita
Comisarul
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="minmaxstore") ==
