== include(page="template/taskheader" task_id="minmaxtree") ==

Poveste şi cerinţă...

Tanaka a rezolvat de curând o problema clasică: dat fiind un arbore cu $N$ vârfuri şi valori pe muchii, el a găsit valoarea maximă sau minimă pe $K$ lanţuri din arbore. În mod interesant, toate aceste rezultate au fost distincte! Din nefericire, valorile iniţiale au fost pierdute.
Dându-se rezultatele lui Tanaka, cât şi structura arborelui original, poţi găsi o atribuire plauzibilă a valorilor pentru toate muchiile? Dacă poţi, Groot se va îndrăgosti de arborele creat şi vei primi $100$ de puncte.

h2. Date de intrare

Fişierul de intrare $minmaxtree.in$ ...

Prima linie a fişierului de intrare $minmaxtree.in$ va conţine numărul $N$.
Următoarele $N - 1$ linii vor conţine perechi de numere $x y$, cu $1 ≤ x, y ≤ N$, ce semnifică că arborele are o muchie de la nodul $x$ la nodul $y$. Nodurile arborelui sunt indexate de la $1$ la $N$.
Următoarea linie a inputului va conţine numărul $K$.
Următoarele $K$ linii vor conţine o descriere a rezultatelor lui Tanaka, un rezultat pe fiecare linie. Un rezultat care semnifică că maximul de pe drumul de la $x$ la $y$ a fost $z$ va fi reprezentat de $M x y z$, şi unul care semnifică că minimul de pe drumul de la $x$ la $y$ a fost $z$ va fi reprezentat de $m x y z$.
Se garantează că muchiile date formează un arbore, şi că toate valorile $z$ sunt distincte.

h2. Date de ieşire

În fişierul de ieşire $minmaxtree.out$ ...

Fişierul de ieşire $minmaxtree.out$ va conţine $N - 1$ linii. Fiecare linie va conţine trei numere $x y v$ care semnifică că în atribuirea ta de valori exită o muchie de la $x$ la $y$ cu greutatea $v$. Aceste muchii ar trebui să coincidă cu muchiile din fişierul de intrare, ignorând ordinea muchiilor. Mai mult, ordinea lui $x$ şi $y$ în cadrul unei muchii nu contează. Această atribuire ar trebui să ducă la rezultatele descrise.
Se garantează că există o atribuire de valori ce duce la rezultatele descrise.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 70.000$
* $1 ≤ K ≤ 70.000$
* $1 ≤ z ≤ 1.000.000.000$
* Pentru $7$ puncte, $N ≤ 1.000$ şi $z ≤ 1.000$.
* Pentru alte $22$ puncte, Tanaka a găsit doar maxime.
* Pentru alte $29$ puncte, oricare două lanţuri pentru care Tanaka a găsit maxime nu se intersectează. De asemenea, oricare două lanţuri pentru care Tanaka a găsit minime nu se intersectează.
 
h2. Exemple

h2. Exemplu

table(example). |_. minmaxtree.in |_. minmaxtree.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4
1 2
2 3
3 4
3
M 1 2 1
m 1 4 0
M 2 3 100
|3 2 100
1 2 1
4 3 0

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="minmaxtree") ==