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$

* <tex> \sum_{i=1}^{N} dist(i, p(i)) </tex> este **maxima**, unde $dist(i, j) =$ lungimea lantului elementar dintre nodurile $i$ si $j$

*
h2. Date de intrare