Đề bài

Paint & Wine là xưởng vẽ đầu tiên tại Zagreb cung cấp những buổi học vẽ thư giãn cùng một ly rượu vang. Trong mỗi buổi học, học viên nhận một chủ đề nhất định và, với sự hỗ trợ của các họa sĩ bậc thầy, thường tạo ra một tác phẩm ấn tượng.

Ante là họa sĩ hướng dẫn, Luka là học viên của anh, và câu chuyện trong bài toán này diễn ra vào một buổi học có phần nhiều rượu hơn bình thường.

Ante nói: "Hãy vẽ cho tôi một cái cây!"

Luka hỏi: "Được thôi. Anh muốn cây gì? Cọ, sồi hay thông?"

Ante đáp: "Tôi muốn một đồ thị vô hướng liên thông không có chu trình!"

Luka nói: "Tôi làm được... Anh còn yêu cầu gì không?"

Ante nói: "Tôi thích mỗi đỉnh kề với không quá ba đỉnh khác!"

Luka đáp: "Ừm, được... Nhưng có rất nhiều cây như vậy."

Ante nói: "Đây là danh sách các cạnh. Tôi muốn đúng cây này!"

Luka đáp: "Được rồi. Nhưng vẫn có nhiều cách vẽ nó."

Ante nói: "Đây là danh sách các điểm trên mặt phẳng mà tôi muốn đặt các đỉnh. Tôi cũng không muốn thấy bất kỳ cặp cạnh nào cắt nhau."

Luka đáp: "Tôi làm ngay!"

Hãy giúp Luka vẽ cây theo đúng yêu cầu của Ante. Cụ thể, bạn được cho một cây mà mỗi đỉnh kề với không quá ba đỉnh khác, cùng một danh sách điểm trên mặt phẳng. Hãy tìm một ánh xạ một-một từ các đỉnh đến các điểm sao cho khi vẽ mỗi cạnh của cây thành đoạn thẳng nối hai điểm tương ứng, không có hai cạnh nào giao nhau, ngoại trừ tại đầu mút chung.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\), đồng thời là số đỉnh của cây và số điểm trên mặt phẳng.

\(N-1\) dòng tiếp theo mô tả các cạnh của cây. Mỗi dòng chứa hai số nguyên \(a\) và \(b\), là nhãn của hai đỉnh được nối bởi cạnh đó. Các đỉnh được đánh số từ \(1\) đến \(N\).

Dữ liệu bảo đảm mỗi đỉnh kề với không quá ba đỉnh khác.

\(N\) dòng tiếp theo mô tả các điểm dùng để vẽ cây. Mỗi dòng chứa hai tọa độ nguyên của một điểm. Không có hai điểm nào có cùng cặp tọa độ và không có ba điểm nào thẳng hàng.

Dữ liệu ra

In một hoán vị của các số nguyên từ \(1\) đến \(N\) trên một dòng. Số thứ \(i\) là nhãn của đỉnh được ánh xạ tới điểm thứ \(i\) trong dữ liệu vào.

Nếu có nhiều lời giải hợp lệ, có thể in bất kỳ lời giải nào. Dữ liệu bảo đảm luôn tồn tại lời giải.

Ràng buộc

Trong tất cả các subtask, tọa độ các điểm là số nguyên từ \(0\) đến \(10^9\).

Phân nhóm

• Subtask 1 (10 điểm): \(3\le N\le 200\,000\) và tồn tại một đa giác lồi nhận tất cả các điểm đã cho làm đỉnh.
• Subtask 2 (15 điểm): \(1\le N\le 4\,000\).
• Subtask 3 (15 điểm): \(1\le N\le 10\,000\).
• Subtask 4 (35 điểm): \(1\le N\le 80\,000\).
• Subtask 5 (25 điểm): \(1\le N\le 200\,000\).

Ví dụ

3
1 2
2 3
10 10
10 20
20 10

1 2 3

5
1 2
1 3
1 4
4 5
10 10
10 30
30 10
30 30
20 25

5 4 2 3 1

6
1 2
2 3
1 4
4 5
4 6
10 60
10 40
40 50
40 30
70 30
70 10

6 5 4 1 2 3