Cum protagonistul nostru, Sorin Pastrama, este seful la bani, acesta isi doreste sa plece in tari straine. Toata lumea stie ca acesta se respecta, asa ca el a ales cea mai de lux companie aeriana si a zis ca va calatori numai cu aceasta. Compania opereaza in $N$ orase mari ale lumii, cu diferite zboruri intre acestea. Mai exact, aceste rute constituie un arbore cu $N$ noduri, cu radacina in nodul $1$, fiecare muchie (cate un zbor in ambele sensuri) avand cate un cost. Cum Pastrama nu este foarte bun la matematica (deoarece el a urmat scola de smecherie), va roaga sa-l ajutati cu urmatoarele $M$ operatii:
* $1 x c$ -> costul muchiei de la $x$ la tatal lui $x$ devine $c$ ( $2 ≤ x ≤ N$ )

* $2 x y$ -> Pastrama vrea sa plece din nodul $x$ si sa ajunga in nodul $y$. La fiecare pas, daca el se afla intr-un nod anume diferit de $y$, el va alege cu probabilitate egala un vecin al acestui nod si va merge acolo. Pastrama ar vrea sa stie care este costul mediu (expected value) al acestei calatori **( $y$ este un stramos al lui $x$ )**.

* $2 x y$ -> Pastrama vrea sa plece din nodul $x$ si sa ajunga in nodul $y$. La fiecare pas, daca el se afla intr-un nod anume diferit de $y$, el va alege cu probabilitate egala un vecin al acestui nod si va merge acolo. Pastrama ar vrea sa stie care este costul mediu (expected value) al acestei calatori ( **$y$ este un stramos al lui $x$** ).

h2. Date de intrare