원피스

고아 왕국은 $1$부터 $n$까지 번호가 붙은 $n$개의 섬과 $n - 1$개의 양방향 다리로 이루어져 있다. 섬과 다리는 트리 구조를 이룬다. 일부 섬에는 값진 보물이 있고, 루피는 모든 섬의 보물을 찾으러 나섰다.

보물 찾기를 쉽게 하려고 루피는 마을 상인에게 탐지기를 샀다. 탐지기는 원래 각 섬에서 가장 가까운 보물까지의 거리(다리 개수)를 보여 주어야 했지만, 심하게 고장 나서 가장 먼 보물까지의 거리를 보여 준다.

그래도 루피는 고장 난 탐지기가 각 섬에 보여 준 거리를 모두 기록해 두었고, 어쩌면 모든 것을 잃은 건 아닐지 기대하고 있다. 이제 어느 섬에 보물이 있을 확률이 더 높은지 궁금해한다.

탐지기가 각 섬에 보여 준 거리를 아는 상황에서, 루피를 도와 $n$개의 섬을 보물이 있을 확률이 높은 순서에서 낮은 순서로 정렬하라. 처음에는 각 섬이 독립적으로 $50\%$의 확률로 보물을 가진다고 가정할 수 있다. 다시 말해, 섬의 모든 부분집합이 보물이 있는 섬들의 집합이 될 확률이 같다.

첫째 줄에 섬의 수 $n$이 주어진다. ($1 \le n \le 250\,000$) 다음 $n - 1$개 줄에 다리 정보가 주어진다. 각 다리는 서로 다른 두 섬을 연결한다. 마지막 줄에는 탐지기가 각 섬에 보여 준 거리 $n$개가 음이 아닌 정수로 주어진다.

입력 데이터와 일치하는 비어 있지 않은 부분집합이 적어도 하나 존재함이 보장된다.

보물이 있을 확률이 높은 섬부터 낮은 섬까지의 순서로 $n$개의 섬 번호를 순열로 출력한다. 두 섬의 확률이 같으면 번호가 작은 섬을 먼저 출력한다.

첫 번째 예제에서 섬 $2$로부터 거리가 $2$인 섬은 $3$뿐이므로 섬 $3$에는 반드시 보물이 있다. 섬 $4$와 $5$의 확률은 각각 $2/3$이고, 섬 $1$과 $2$의 확률은 $1/2$이다.

두 번째 예제에서 가능한 경우는 섬 $2$에만 보물이 있는 경우뿐이다.