== include(page="template/taskheader" task_id="tractomarm") ==
Toată lumea îl ştie pe TractoMarm, tractoristul suprem, cel care bagă comenzi in Vim mai repede decât pot alţii să citească. Zilele trecute, TractoMarm a dat dat peste următoarea problemă: fiind dat un arbore (graf conex aciclic) cu $N$ noduri, el ar dori să alfe suma distanţelor minime de la nodul $1$ la toate celelalte noduri. Mai mult decat atat, el isi pune $M$ intrebari de forma: _Daca as adauga o muchie intre $x$ si $y$ in arborele meu (astfel formandu-se un ciclu, si posibil modificandu-se niste distante), care ar fi noua suma a distantelor minime de la nodul $1$ la celelalte?_
Deoarece aceasta problema nu este un tractor suficient de mare pentru TractoMarm, el s-a decis sa v-o dea voua spre rezolvare!
Toată lumea îl ştie pe TractoMarm, tractoristul suprem, cel care bagă comenzi in Vim mai repede decât pot alţii să citească. Zilele trecute, TractoMarm a dat dat peste următoarea problemă: fiind dat un arbore (graf conex aciclic) cu $N$ noduri, el ar dori să alfe suma distanţelor minime de la nodul $1$ la toate celelalte noduri. Mai mult decât atât, el îşi pune $M$ întrebări de forma: _Dacă aş adăuga o muchie între $x$ şi $y$ în arborele meu (astfel formându-se un ciclu, şi posibil modificându-se nişte distanţe), care ar fi noua sumă a distanţelor minime de la nodul $1$ la celelalte?_
Deoarece această problemă nu este un tractor suficient de mare pentru TractoMarm, el s-a decis să v-o dea vouă spre rezolvare!
h2. Date de intrare
Fişierul de intrare $tractomarm.in$ contine pe prima linie numarul intreg $N$, numarul de noduri din arbore.
Pe urmatoarele N - 1 linii se afla perechi de numere $a$ si $b$ separate prin spatiu, semnificand ca exista o muchie intre $a$ si $b$ in arbore.
Pe urmatoarea linie se afla $M$, numarul de interbari ale lui TractoMarm.
In continuare, pe $M$ linii, se afla cate doua numere $x$ si $y$, reprezentand o intrebare a lui TractoMarm la care voi trebuie sa raspundeti ("_Daca as aduga o muchie de la $x$ la $y$ in arbore care ar fi suma distatelor minime de la nodul $1$ la celalte noduri?_").
Fişierul de intrare $tractomarm.in$ conţine pe prima linie numărul întreg $N$, numărul de noduri din arbore.
Pe următoarele N - 1 linii se află perechi de numere $a$ şi $b$ separate prin spaţiu, semnificând că există o muchie între $a$ şi $b$ în arbore.
Pe următoarea linie se află $M$, numărul de întrebări ale lui TractoMarm.
În continuare, pe $M$ linii, se află câte două numere $x$ şi $y$, reprezentând o întrebare a lui TractoMarm la care voi trebuie să raspundeţi ("_Dacă aş adăuga o muchie de la $x$ la $y$ în arbore care ar fi suma distaţelor minime de la nodul $1$ la celelalte noduri?_").
h2. Date de ieşire
În fişierul de ieşire $tractomarm.out$ contime $M$ linii, cate una pentru fiecare interbare din fisierul de intrare.
În fişierul de ieşire $tractomarm.out$ va conţine $M$ linii, câte una pentru fiecare întrebare din fişierul de intrare.
h2. Restricţii
* $3$ ≤ $N$ ≤ $250000$
* $1$ ≤ $M$ ≤ $400000$
* $1$ ≤ $x$, $y$, $a$, $b$ ≤ $N$
* $3 ≤ N ≤ 250000$
* $1 ≤ M ≤ 400000$
* $1 ≤ x, y, a, b ≤ N$
* *Atentie!* TractoMarm vă aminteşte că memoria disponibilă pentru stivă este de maxim 8 MB!
h2. Exemplu
table(example). |_. tractomarm.in |_. tractomarm.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 6
1 2
1 3
2 4
4 5
4 6
3
2 3
3 6
1 6
| 10
9
8
|
