Vương quốc Goa là một mạng lưới gồm $n$ hòn đảo (được đánh số từ $1$ đến $n$), kết nối với nhau bởi $n - 1$ cây cầu hai chiều. Mạng lưới này có cấu trúc là một cây. Một số hòn đảo có chứa kho báu quý giá, và Luffy đang thực hiện hành trình tìm kiếm kho báu từ tất cả các hòn đảo.

Để hỗ trợ việc săn tìm kho báu, cậu ấy đã mua một chiếc máy dò từ một thương nhân địa phương. Đáng lẽ chiếc máy phải hiển thị khoảng cách từ mỗi hòn đảo đến kho báu gần nhất (tính theo số lượng cây cầu); tuy nhiên, có vẻ như nó đã bị hỏng nặng và lại hiển thị khoảng cách từ mỗi hòn đảo đến kho báu xa nhất!

Dù vậy, cậu ấy vẫn giữ lại các khoảng cách mà chiếc máy dò bị hỏng đã hiển thị cho mỗi hòn đảo, với hy vọng rằng có lẽ không phải mọi thứ đều đã mất. Giờ đây, cậu ấy tự hỏi những hòn đảo nào có khả năng chứa kho báu cao hơn.

Nhiệm vụ của bạn là giúp Luffy sắp xếp $n$ hòn đảo theo thứ tự từ cao đến thấp về xác suất chứa kho báu, dựa trên việc cậu ấy đã biết khoảng cách mà máy dò hiển thị cho mỗi hòn đảo. Ban đầu, bạn có thể giả định rằng mỗi hòn đảo độc lập với nhau và có 50% khả năng chứa kho báu; nói cách khác, mọi tập hợp con các hòn đảo đều có khả năng như nhau để trở thành tập hợp các hòn đảo chứa kho báu.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa $n$ ($1 \le n \le 250\,000$), số lượng hòn đảo. $n - 1$ dòng tiếp theo mô tả các cây cầu. Mỗi cây cầu kết nối hai hòn đảo phân biệt. Cuối cùng, dòng cuối cùng chứa $n$ số nguyên không âm, là các khoảng cách (tính theo số lượng cây cầu) mà máy dò của Luffy hiển thị cho mỗi hòn đảo.

Đảm bảo rằng luôn tồn tại ít nhất một tập hợp con không rỗng phù hợp với dữ liệu đầu vào.

Dữ liệu ra

Xuất ra một hoán vị có kích thước $n$, là thứ tự các hòn đảo từ cao đến thấp về xác suất chứa kho báu. Nếu hai hòn đảo có cùng xác suất chứa kho báu, hãy xuất chúng theo thứ tự tăng dần của ID.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

3 4 5 1 2

Ghi chú

Trong ví dụ đầu tiên, hòn đảo 3 bắt buộc phải chứa kho báu, vì đó là hòn đảo duy nhất cách hòn đảo 2 một khoảng cách là 2. Các hòn đảo 4 và 5 đều có xác suất là $2/3$, trong khi các hòn đảo 1 và 2 có xác suất là $1/2$.

Dữ liệu vào 2

4
2 1
3 2
3 4
1 0 1 2

Dữ liệu ra 2

2 1 3 4

Ghi chú

Trong ví dụ thứ hai, kịch bản duy nhất có thể xảy ra là hòn đảo 2 là hòn đảo duy nhất chứa kho báu.