== include(page="template/taskheader" task_id="curatenie") ==
Poveste şi cerinţă...
Vampirii din Twilight nu s-au mulţumit cu numărul imens de fani foarte înfocaţi. Asa ca au atacat membrii organizatori ai Balulului Bobocilor al Facultăţii de Matematică şi Informatică din Universitatea din Bucureşti. Transformarea a început cu un singur individ. Apoi acesta a transformat la rândul sau cel mult doi indivizi, deoarece fiecare vampir are doua transformări la dispoziţie, şi tot asa mai departe fiecare individ a transformat indivizi, pana când toţi membrii Asociaţiei Studenţilor la Matematica şi Informatica au devenit vampiri. Astfel, ii putem aşeza ca într-un arbore binar, unde rădăcina este primul individ transformat, fii unui nod sunt exact membrii pe care acesta ia transformat. Problema lor, a vampirilor, este ca au făcut mizerie prin aceste transformări. Şi trebuie sa facă curăţenie. Tot ce ştiu ei e ca au doua tipuri de-a face curăţenie, şi anume:
$1)$ dacă este rândul lui $X$ sa facă curăţenie, acesta îl pune pe primul transformat sa facă curăţenie, dacă exista, apoi face el curat, iar apoi îl va pune pe cel de-al doilea, dacă exista.
$2)$ dacă este rândul lui $X$ sa facă curăţenie, va face el curat, după care acesta îl pune pe primul transformat, dacă exista, sa facă curăţenie, iar apoi îl va pune pe cel de-al doilea, dacă exista.
Date cele doua ordini de a face curăţenie, voi trebuie sa aflaţi cine pe cine a transformat.
h2. Date de intrare
Fişierul de intrare $curatenie.in$ ...
Fişierul de intrare $curatenie.in$ conţine pe prima linie $N$, numărul de membrii transformaţi, iar pe următoarele doua linii cele doua ordini: pe linia a doua se va afla cea de tipul $1$, iar pe linia a treia se va afla cea de tipul $2$.
h2. Date de ieşire
În fişierul de ieşire $curatenie.out$ ...
În fişierul de ieşire $curatenie.out$ se afla N linii, unde linia $i$ conţine $2$ numere, reprezentând cei doi indivizi transformaţi de membrul $i$. Daca unul din ei nu exista, se va afişa $0$ pentru respectivul.
h2. Restricţii
h2. Restricţii şi precizari
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 500.000$
* Numerele din fisierul de intrare sunt intre $1$ si $N$.
* *Atenţie la faptul ca un individ poate alege sa nu transforme pe nimeni, sau sa îşi folosească doar prima sau doar a doua transformare, contând ordinea.*
h2. Exemplu
table(example). |_. curatenie.in |_. curatenie.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
| 4
1 4 2 3
3 1 2 4
| 0 2
4 0
1 0
0 0
|
| 7
4 2 5 1 3 7 6
1 2 4 5 3 6 7
| 2 3
4 5
0 6
0 0
0 0
7 0
0 0
|
== include(page="template/taskfooter" task_id="curatenie") ==
