Fişierul intrare/ieşire:curatenie.in, curatenie.outSursăFMI No Stress 3
AutorDragos OpricaAdăugată deDraStiKDragos Oprica DraStiK
Timp execuţie pe test0.75 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Curatenie

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.

Date de intrare

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.

Date de ieşire

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

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.

Exemplu

curatenie.incuratenie.out
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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?