Le royaume de Goa est un réseau de $n$ îles (identifiées par des numéros de $1$ à $n$), reliées par $n - 1$ ponts bidirectionnels. Le réseau est structuré sous forme d'arbre. Certaines îles contiennent des trésors précieux, et Luffy est en quête de trouver les trésors de toutes les îles.

Afin de faciliter la chasse au trésor, il a acheté un détecteur à un marchand local. Le détecteur aurait dû afficher la distance de chaque île au trésor le plus proche (en nombre de ponts) ; cependant, il semble être horriblement défectueux et affiche plutôt la distance de chaque île au trésor le plus éloigné !

Néanmoins, il a conservé les distances indiquées par son détecteur défectueux pour chacune des îles, espérant que tout n'est peut-être pas perdu. Il se demande maintenant quelles îles ont une plus grande probabilité de contenir un trésor.

Votre tâche est d'aider Luffy en classant les $n$ îles par ordre décroissant de probabilité de contenir un trésor, sachant qu'il connaît désormais les distances affichées par le détecteur pour chacune des $n$ îles. Initialement, vous pouvez supposer que chacune des îles avait indépendamment $50\,\%$ de chances de contenir un trésor ; en d'autres termes, chaque sous-ensemble d'îles avait la même probabilité d'être le sous-ensemble des îles contenant un trésor.

Entrée

La première ligne de l'entrée contient $n$ ($1 \le n \le 250\,000$), le nombre d'îles. Les $n - 1$ lignes suivantes décrivent les ponts. Chaque pont relie deux îles distinctes. Enfin, la dernière ligne contient $n$ entiers non négatifs, les distances (en nombre de ponts) affichées sur le détecteur de Luffy pour chacune des îles.

Il est garanti qu'il existe au moins un sous-ensemble non vide cohérent avec les données d'entrée.

Sortie

Affichez une permutation de taille $n$, l'ordre des îles de la plus haute à la plus basse probabilité de contenir un trésor. Si deux îles ont la même probabilité de contenir un trésor, affichez-les par ordre croissant de leurs identifiants.

Exemples

Entrée 1

5
1 2
1 3
2 4
2 5
2 2 3 3 3

Sortie 1

3 4 5 1 2

Entrée 2

4
2 1
3 2
3 4
1 0 1 2

Sortie 2

2 1 3 4

Remarque

Dans le premier exemple, l'île 3 doit contenir un trésor, car c'est la seule à une distance de 2 de l'île 2. Les îles 4 et 5 ont chacune une probabilité de $2/3$, tandis que les îles 1 et 2 ont une probabilité de $1/2$.

Dans le second exemple, le seul scénario possible est que l'île 2 soit la seule à contenir un trésor.