고아 왕국은 $n$개의 섬(1부터 $n$까지의 번호로 식별됨)이 $n-1$개의 양방향 다리로 연결된 네트워크입니다. 이 네트워크는 트리 구조로 되어 있습니다. 일부 섬에는 귀중한 보물이 숨겨져 있으며, 루피는 모든 섬의 보물을 찾기 위한 모험을 떠났습니다.

보물 찾기를 쉽게 하기 위해 루피는 지역 상인에게서 탐지기를 샀습니다. 이 탐지기는 각 섬에서 가장 가까운 보물까지의 거리(다리의 개수)를 보여주어야 하지만, 고장 난 탓에 각 섬에서 가장 먼 보물까지의 거리를 보여줍니다!

그럼에도 불구하고 루피는 고장 난 탐지기가 각 섬에 대해 보여준 거리 정보를 기록해 두었고, 혹시나 모든 것을 잃은 것은 아닐까 하는 희망을 품고 있습니다. 이제 그는 탐지기가 보여준 각 섬의 거리 정보를 알고 있을 때, 어떤 섬이 보물을 포함하고 있을 확률이 더 높은지 궁금해합니다. 루피를 도와 $n$개의 섬을 보물을 포함할 확률이 높은 순서대로 나열해 주세요. 처음에 각 섬은 독립적으로 50%의 확률로 보물을 포함하고 있다고 가정할 수 있습니다. 즉, 모든 섬의 부분집합이 보물이 있는 섬의 집합일 확률은 동일합니다.

입력

첫 번째 줄에는 섬의 개수 $n$ ($1 \le n \le 250\,000$)이 주어집니다. 이어지는 $n-1$개의 줄에는 다리에 대한 정보가 주어집니다. 각 다리는 서로 다른 두 섬을 연결합니다. 마지막 줄에는 각 섬에 대해 루피의 탐지기가 보여준 거리(다리의 개수)를 나타내는 $n$개의 음이 아닌 정수가 주어집니다.

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

출력

보물을 포함할 확률이 높은 순서대로 섬의 번호를 나열한 크기 $n$의 순열을 출력하세요. 두 섬의 보물 포함 확률이 같다면, 섬의 번호가 작은 순서대로 출력하세요.

예제

입력 1

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

출력 1

3 4 5 1 2

입력 2

4
2 1
3 2
3 4
1 0 1 2

출력 2

2 1 3 4

참고

첫 번째 예제에서, 섬 3은 섬 2로부터 거리가 2인 유일한 섬이므로 반드시 보물을 포함해야 합니다. 섬 4와 5는 각각 $2/3$의 확률을 가지며, 섬 1과 2는 각각 $1/2$의 확률을 가집니다.

두 번째 예제에서, 가능한 유일한 시나리오는 섬 2만이 보물을 포함하고 있는 경우입니다.