Vẽ cây lên các điểm

Cho một cây gồm $n$ đỉnh và $n$ điểm trên mặt phẳng, trong đó không có ba điểm nào thẳng hàng.

Nhiệm vụ của bạn là vẽ cây đã cho lên mặt phẳng, dùng các điểm đã cho làm vị trí của các đỉnh. Cụ thể, mỗi đỉnh của cây phải được đặt vào đúng một điểm, và mỗi điểm phải ứng với đúng một đỉnh. Nếu hai đỉnh của cây được nối bởi một cạnh thì ta vẽ một đoạn thẳng nối hai điểm tương ứng.

Cách đặt phải thỏa mãn: hai đoạn thẳng ứng với hai cạnh không kề nhau (không có đỉnh chung) thì không được có điểm chung nào; hai đoạn thẳng ứng với hai cạnh kề nhau (có chung một đỉnh) thì chỉ được cắt nhau đúng tại điểm chung đó.

Dữ liệu đảm bảo luôn tồn tại một cách đặt hợp lệ.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$, số đỉnh của cây (cũng là số điểm được chọn).
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_i$ và $v_i$, cho biết cạnh thứ $i$ nối hai đỉnh $u_i$ và $v_i$.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $x_i$ và $y_i$, là tọa độ của điểm thứ $i$.

Dữ liệu ra

In ra $n$ số nguyên phân biệt từ $1$ đến $n$: số thứ $i$ là chỉ số của đỉnh cây được đặt tại điểm thứ $i$.

Nếu có nhiều cách đặt hợp lệ, in ra bất kỳ cách nào.

Ràng buộc

• $1\le n\le 1500$
• $1\le u_i,v_i\le n$, $u_i\ne v_i$
• $-{10}^9\le x_i,y_i\le {10}^9$
• Không có ba điểm nào thẳng hàng.

Ví dụ