h2. Cerinta

Scrieti un program care primeste N, M, structura angajatilor si cele M operatii iar pentru fiecare operatie de tipul 2 afiseaza valoarea ceruta.

Scrieti un program care primeste {$N$}, {$M$}, structura angajatilor si cele $M$ operatii iar pentru fiecare operatie de tipul $2$ afiseaza valoarea ceruta.

h2. Date de Intrare

Fisierul arbore.in contine pe prima linie numerele N si M separate printr-un spatiu.
 
Urmatoarele N - 1 linii contin cate doua numere intregi p si q cu semnificatia ca "exista relatie directa intre angajatul p si angajatul q".
 
Urmatoarele M linii cotin cate o operatie pe linie. Primul numar de pe linie este 1 sau 2, si semnifica tipul operatiei ce va fi descrisa. In cazul unei operatii de tip 1 vor urma numerele p si s, iar in cazul unei operatii de tip 2 va urma un singur numar s.

Fisierul $arbore.in$ contine pe prima linie numerele $N$ si $M$ separate printr-un spatiu.
Urmatoarele $N-1$ linii contin cate doua numere intregi $p$ si $q$ cu semnificatia ca "exista relatie directa intre angajatul $p$ si angajatul {$q$}".
Urmatoarele $M$ linii cotin cate o operatie pe linie. Primul numar de pe linie este $1$ sau {$2$}, si semnifica tipul operatiei ce va fi descrisa. In cazul unei operatii de tip $1$ vor urma numerele $p$ si {$s$}, iar in cazul unei operatii de tip $2$ va urma un singur numar {$s$}.

h2. Date de Iesire

Fisierul arbore.out contine pentru fiecare operatie de tip 2 indicele unui angajat care a primit suma respectiva de bani pana la momentul respectiv. In cazul in care nu exista un asemenea angajat, se cere sa se afiseze -1. Nu are importanta indicele carui angajat il veti afisa, atata timp cat acesta a primit suma s.

Fisierul $arbore.out$ contine pentru fiecare operatie de tip $2$ indicele unui angajat care a primit suma respectiva de bani pana la momentul respectiv. In cazul in care nu exista un asemenea angajat, se cere sa se afiseze {$-1$}. Nu are importanta indicele carui angajat il veti afisa, atata timp cat acesta a primit suma {$s$}.

h2. Restrictii si precizari

&#159; 1 <= N, M <= 100 000
 
&#159; pentru o operatie de tipul 1 avem 1 <= s <= 10
 
&#159; pentru o operatie de tipul 2 avem 0 <= s <= 1 000 000
 
&#159; 50% dintre testele folosite la evaluare nu vor contine mai mult de 100 de operatii de tip 2

* $1 ≤ N, M ≤ 100 000$
* pentru o operatie de tipul $1$ avem $1 ≤ s ≤ 10$
* pentru o operatie de tipul $2$ avem $0 ≤ s ≤ 1 000 000$
* $50%$ dintre testele folosite la evaluare nu vor contine mai mult de $100$ de operatii de tip $2$

h2. Exemplu

arbore.in arbore.out
6 6 2
 
1 2 1
 
1 3 3
 

table(example). |_. arbfind.in |_. arbfind.out |
| 6 6
1 2
1 3

3 4

3 5

4 6

1 1 1

1 2 4

2 5

2 1

1 3 3

2 4

| 2
1
3 |

 
 
References
 
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/arbore/enunt_files/filelist.xml

==Include(page="template/taskfooter" task_id="arbore")==