El Reino de Goa es una red de $n$ islas (identificadas por números del 1 al $n$), conectadas por $n - 1$ puentes bidireccionales. La red tiene estructura de árbol. Algunas islas contienen tesoros valiosos, y Luffy está en una misión para encontrar los tesoros de todas las islas.

Para facilitar la búsqueda del tesoro, compró un detector a un comerciante local. El detector debería haber mostrado la distancia desde cada isla hasta el tesoro más cercano (en número de puentes); sin embargo, parece estar terriblemente estropeado y, en su lugar, muestra la distancia desde cada isla hasta el tesoro más lejano.

No obstante, conservó las distancias que su detector estropeado mostró para cada una de las islas, con la esperanza de que tal vez no todo esté perdido. Ahora se pregunta qué islas tienen una mayor probabilidad de contener un tesoro.

Tu tarea es ayudar a Luffy ordenando las $n$ islas, de mayor a menor probabilidad de contener un tesoro, dado que ahora conoce las distancias mostradas por el detector para cada una de las $n$ islas. Inicialmente, puedes asumir que cada una de las islas tenía independientemente un 50% de probabilidad de contener un tesoro; en otras palabras, cualquier subconjunto de islas tenía la misma probabilidad de ser el subconjunto de islas con tesoros.

Entrada

La primera línea de la entrada contiene $n$ ($1 \le n \le 250\,000$), el número de islas. Las siguientes $n - 1$ líneas describen los puentes. Cada puente conecta dos islas distintas. Finalmente, la última línea contiene $n$ enteros no negativos, las distancias (en número de puentes) mostradas en el detector de Luffy para cada una de las islas.

Se garantiza que existe al menos un subconjunto no vacío que es consistente con los datos de entrada.

Salida

Imprime una permutación de tamaño $n$, el orden de las islas de mayor a menor probabilidad de contener un tesoro. Si dos islas tienen la misma probabilidad de contener un tesoro, imprímelas en orden creciente de sus identificadores.

Ejemplos

Entrada 1

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

Salida 1

3 4 5 1 2

Entrada 2

4
2 1
3 2
3 4
1 0 1 2

Salida 2

2 1 3 4

Nota

En el primer ejemplo, la isla 3 debe contener un tesoro, ya que es la única a distancia 2 de la isla 2. Las islas 4 y 5 tienen una probabilidad de 2/3 cada una, mientras que las islas 1 y 2 tienen una probabilidad de 1/2.

En el segundo ejemplo, el único escenario posible es que la isla 2 sea la única que contiene un tesoro.