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

Poveste şi cerinţă...

Se dau doi arbori neorientaţi cu $N$ noduri etichetate de la $1$ la $N$ şi costuri pe muchii. Primul arbore se numeşte TREN, iar al doilea se numeşte BUS. Pentru două noduri $A$ şi $B$ şi un arbore $T$ definim $d(A,B,T) =$ valoarea maximă a unei muchii de pe drumul elementar dintre nodurile $A$ şi $B$ în arborele $T$.
Suntem interesaţi de perechile de valori $X$ şi $Y$ cu proprietatea că $d(X,Y,TREN)+d(X,Y,BUS)$ este minim posibil.
În funcţie de valoarea unui parametru $C$ din datele de intrare, trebuie să afişaţi suma minimă cerută, respectiv numărul de perechi de valori $(X,Y)$ care se realizează această valoare minimă.

h2. Date de intrare

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

Pe primul rând al fişierului de intrare $trenbus.in$ se găsesc numerele naturale $C$ şi $N$.
Pe următoarele $N-1$ rânduri se găsesc muchiile neorientate care descriu arborele TREN, iar pe următoarele $N-1$ rânduri se găsesc muchiile neorientate care descriu arborele BUS. Fiecare muchie este descrisă de 3 numere naturale $a b c$, reprezentând capetele muchiei respectiv costul.

h2. Date de ieşire

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

Pe singurul rând al fişierului de ieşire $trenbus.out$ se vor tipări:
   - dacă $C=1$, doar suma cerută,
   - dacă $C=2$, suma cerută şi numărul de perechi separate printr-un spaţiu.
 

h2. Restricţii

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

* $1 ≤ N ≤ 100 000$
* $1 ≤ c ≤ 1 000 000 000$
* Pentru teste în valoare de $10$ puncte $C=1$ si $N ≤ 100$
* Pentru alte teste în valoare de $45$ puncte $C=1$ si $N ≤ 50 000$
* Pentru alte teste în valoare de $20$ puncte $C=1$ si $N ≤ 100 000$
* Pentru alte teste în valoare de $12$ puncte $C=2$ si $N ≤ 50 000$
* Pentru alte teste în valoare de $13$ puncte $C=2$ si $N ≤ 100 000$

h2. Exemplu

table(example). |_. trenbus.in |_. trenbus.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

table(example). |_. trenbus.in |_. trenbus.out |_. Explicaţie |
| 1 3
  1 2 5
  2 3 6
  1 3 1
  2 3 2
| 7
| C=1
  Se afişează doar suma minimă.
  Generată de x = 1, y = 2 sau respectiv x = 1, y = 3.
|
| 2 5
  1 2 2
  2 5 3
  2 4 7
  2 3 2
  1 2 4
  2 3 4
  3 4 3
  4 5 2
| 6 4
| C=2
  Suma minimă este 6, iar numărul perechilor de noduri ce generează această sumă minimă este 4.
|

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