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 muchiei $i$ va avea valoarea finala egala cu $( val~i~ * alfa [ val~i~ ] ) % 100003.

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 muchiei $i$ va avea valoarea finala egala cu $( val ~i~ * alfa [ val ~i~ ] ) % 100003.

h2. Date de intrare