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

Cu totii stim ca dedicatiile la o petrecere sunt foarte scumpe. Marele artist Sorin Pastrama v-a propus un targ: daca il ajutati la rezolvarea urmatoarei probleme el va va face cate decicatii doriti la urmatoarea petrecere, **PE GRATIS**. Problema suna cam asa:

Cu totii stim ca dedcatiile la o petrecere sunt foarte scumpe. Marele artist Sorin Pastrama v-a propus un targ: daca il ajutati la rezolvarea urmatoarei probleme el va va face cate decicatii doriti la urmatoarea petrecere, **PE GRATIS**. Problema suna cam asa:

Se da un arbore cu $N$ noduri. Se garanteaza ca oricum ai alege un nod pe care sa il elimini din arbore, atunci exista cel putin un subarbore din cei rezultati care are marimea <tex> \geq \left\lfloor\frac{N+1}{2}\right\rfloor </tex>.

Fie $val$~$i$~ egal cu valoarea muchiei $i$. Initial $val$~$i$~ = $0$ ( $1 &le; i &le; N-1$ ). Vom lua fiecare pereche de noduri $1 &le; x < y &le; N$ si vom incrementa cu $1$ valoarea fiecarei muchii de pe drumul de la $x$ la $y$. Vom sorta muchiile **descrescator** dupa valoarea acestora (iar in caz de egalitate, crescator dupa indicele muchiei) si le vom normaliza. Adica prima muchie din sortare va avea valoarea egala cu $0$, a doua muchie va avea valoarea egala cu $1$, $...$, ultima muchie din sortare va avea valoarea egala cu $N-2$. Acum, valoarea finala a muchiei $i$ va fi egala cu $( $val$~i~ * alfa[$val$~i~] ) % 100003$, unde $alfa$ este un vector de lungime $N-1$ dat in input.

Fie $val$~$i$~ egal cu valoarea muchiei $i$. Initial $val$~$i$~ = $0$ ( $1 &le; i &le; N-1$ ). Vom lua fiecare pereche de noduri $1 &le; x < y &le; N$ si vom incrementa cu $1$ valoarea fiecarei muchii de pe drumul de la $x$ la $y$. Vom sorta muchiile **descrescator** dupa valoarea acestora (iar in caz de egalitate, crescator dupa indicele muchiei) si le vom normaliza. Adica prima muchie din sortare va avea valoarea egala cu $0$, a doua muchie va avea valoarea egala cu $1$, ..., ultima muchie din sortare va avea valoarea egala cu $N-2$. Acum, valoarea finala a muchiei $i$ va fi egala cu $( $val$~i~ * alfa[$val$~i~] ) % 100003$, unde $alfa$ este un vector de lungime $N-1$ dat in input.

Se cere sa se afiseze o permutare $p(1), p(2), ..., p(N)$ a numerelor de la $1$ la $N$ care satisface urmatoarele proprietati:

* <tex> \sum_{i=1}^{N} dist(i, p(i)) </tex> $este **maxima**, unde dist(i, j) = lungimea lantului elementar dintre nodurile i si j$
* $Sirul de perechi { (p(1) -> 1, p(1)) , (p(2) -> 2, p(2)) , ... , (p(N) -> N, p(N)) } este **minim lexicografic**, unde p(i) -> i reprezinta sirul valorilor finale muchiilor de pe drumul de la nodul p(i) la nodul i, in oridnea in care ele apar pe drum$

* <tex> \sum_{i=1}^{N} dist(i, p(i)) </tex> este **maxima**, unde $dist(i, j) = lungimea lantului elementar dintre nodurile i si j$
* Sirul de perechi ${ (p(1) -> 1, p(1)) , (p(2) -> 2, p(2)) , ... , (p(N) -> N, p(N)) }$ este **minim lexicografic**, unde $p(i) -> i$ reprezinta sirul valorilor finale muchiilor de pe drumul de la nodul $p(i)$ la nodul $i$

h2. Date de intrare

Fişierul de intrare $dedicatie.in$ contine pe prima linie numarul natural $N$, cu semnificatia din enunt. Pe urmatoarele $N-1$ linii se afla cate doua numere naturale $x$ si $y$ cu semnificatia ca exista o muchie intre aceste doua noduri. Pe ultima linie a fisierului de intrare se afla cele $N-1$ elemente ale vectorului $alfa$ separate prin cate un spatiu (vectorul este indexat de la $0$).

Fişierul de intrare $dedicatie.in$ contine pe prima linie numarul natural $N$, cu semnificatia din enunt. Pe urmatoarele $N-1$ linii se afla cate doua numere naturale $x$ si $y$ cu semnificatia ca exista o muchie intre aceste doua noduri. Pe ultima linie a fisierului de intrare se afla cele $N-1$ elemente ale vectorului $alfa$ separate prin cate un spatiu (vectorul este indexat de la 0).

h2. Date de ieşire

* $1 ≤ N ≤ 10^5^$
* $1 &le; alfa[i] < 100003, 0 &le; i &le; N-2$

* $O pereche (a, b) este mai mica ca o pereche (x, y) daca a < x sau daca a = x si b < y$
* $Un sir$ ${ $a$~1~, $a$~2~, ..., $a$~k~ }$ $este mai mic lexicografic ca sirul$ ${ $b$~1~, $b$~2~, ..., $b$~s~ }$ $daca exista o pozitie$ $1 &le; i &le; min(k, s) astfel incat $a$~1~ = $b$~1~, $a$~2~ = $b$~2~, ..., $a$~i-1~ = $b$~i-1~ si $a$~i~ < $b$~i~ sau daca $a$~1~ = $b$~1~, $a$~2~ = $b$~2~, ..., $a$~k~ = $b$~k~ si k < s$
* Replica preferata a lui Sorin Pastrama este: _"Ai gresit buzunarul baiatul meu!"_

h2. Exemplu

h3. Explicaţie

Dupa ce parcurgem fiecare drum si incrementam cu $1$ muchiile, valorile acestora sunt:
$muchia 1 (5 -> 4): 9$
$muchia 2 (4 -> 2): 5$
$muchia 3 (3 -> 1): 5$
$muchia 4 (4 -> 6): 5$
$muchia 5 (1 -> 5): 8$

Dupa ce parcurgem fiecare drum si incrementam cu 1 muchiile, valorile acestora sunt:
muchia 1 (5 -> 4): 9
muchia 2 (4 -> 2): 5
muchia 3 (3 -> 1): 5
muchia 4 (4 -> 6): 5
muchia 5 (1 -> 5): 8

Dupa normalizare, muchiile au valorile:

$muchia 1 (5 -> 4): 0$
$muchia 2 (4 -> 2): 2$
$muchia 3 (3 -> 1): 3$
$muchia 4 (4 -> 6): 4$
$muchia 5 (1 -> 5): 1$

muchia 1 (5 -> 4): 0
muchia 2 (4 -> 2): 2
muchia 3 (3 -> 1): 3
muchia 4 (4 -> 6): 4
muchia 5 (1 -> 5): 1

Dupa inmultirea cu $alfa$, muchiile au valorile finale:

$muchia 1 (5 -> 4): (0 * 7574) $%$ 100003 = 0$
$muchia 2 (4 -> 2): (2 * 1) $%$ 100003 = 2$
$muchia 3 (3 -> 1): (3 * 66670) $%$ 100003 = 4$
$muchia 4 (4 -> 6): (4 * 25002) $%$ 100003 = 5$
$muchia 5 (1 -> 5): (1 * 2) $%$ 100003 = 2$

muchia 1 (5 -> 4): (0 * 7574) % 100003 = 0
muchia 2 (4 -> 2): (2 * 1) % 100003 = 2
muchia 3 (3 -> 1): (3 * 66670) % 100003 = 4
muchia 4 (4 -> 6): (4 * 25002) % 100003 = 5
muchia 5 (1 -> 5): (1 * 2) % 100003 = 2

Permutarea optima este: $4 5 2 1 6 3$

Permutarea optima este: 4 5 2 1 6 3

<tex> \sum_{i=1}^{6} dist(i, p(i)) = 2 + 2 + 4 + 2 + 2 + 4 = 16</tex> si este maxima
Sirul de perechi este: ${ ({0, 2}, 4) , ({0, 2}, 5) , ({2, 0, 2, 4}, 2) , ({2, 0}, 1) , ({5, 0}, 6) , ({4, 2, 0, 5}, 3) }$ si este minim lexicografic