Problem
Asya rất yêu động vật. Gần đây, cô ấy đã mua n chú mèo con, đưa cho chúng các số nhận dạng từ 1 đến n và đặt chúng vào chuồng. Chuồng chim là một dãy n ô, cũng được đánh số từ 1 đến n. Các ô lân cận được phân tách bằng các phân vùng lưới, tổng cộng có n&trừ; 1 phân vùng trong bao vây. Ban đầu, chính xác một con mèo con với một số lượng định cư trong mỗi ô.
Quan sát những chú mèo con, Asya nhận thấy rằng chúng rất thân thiện và một số cặp mèo con sống trong các phòng giam lân cận thực sự muốn chơi với nhau. Để không tước đi niềm vui này của họ, Asya bắt đầu loại bỏ các vách ngăn giữa các ô liền kề, làm cho chúng lớn hơn.
Vào ngày thứ i, Asya đã làm như sau.
Tôi nhận thấy rằng một số mèo con x
i và y
i, sống trong các ô lân cận vào ngày thứ i, muốn chơi.
Tôi đã loại bỏ vách ngăn giữa các ô này, biến chúng thành một, trong đó tất cả mèo con từ hai ô trước đó đều kết thúc.
Vì Asya đã không trả lại các phân vùng, sau n & trừ 1 ngày, chuồng trở thành một phòng giam duy nhất trong đó tất cả những chú mèo con sống. Là một người rất mô phạm, Asya đã viết ID mèo con x
i và y
i cho mỗi n&trừ 1 ngày trong một nhật ký đặc biệt.
Bạn có một tạp chí với thông tin này, nhưng bạn không biết làm thế nào những chú mèo con được định cư trong các phòng giam ngay từ đầu. Tìm bất kỳ phân phối nào của mèo con trong n ô ban đầu không mâu thuẫn với dữ liệu trong nhật ký.
Đầu vào
Dòng đầu tiên chứa số nguyên n (
\(2 \leq n \leq 150000\)) — số mèo con.
N&trừ1 dòng tiếp theo chứa các cặp số nguyên x
i , y
i (
\(1 \leq x_i , y_i, \leq n,x_i \neq y_i\) ) — số nhận dạng của mèo con, giữa các ô mà phân vùng đã bị xóa vào ngày thứ i. Đảm bảo rằng mèo con xi và yi không ở trong cùng một ô do kết quả của việc hợp nhất ô trước đó.
Dấu ấn
In ra n số nguyên phân biệt p
i (
\(1 \leq p_i \leq n\)), trong đó p
i — mã định danh của chú mèo con ban đầu sống ở ô số i. Nếu có nhiều câu trả lời khả thi, hãy in bất kỳ câu nào trong số đó.
Lưu ý
Ví dụ, trong câu trả lời, một trong những khu định cư ban đầu có thể có của mèo con được đưa ra, có những câu trả lời khác. Hình ảnh bên dưới cho thấy cách các ô được hợp nhất cho vị trí ban đầu của những chú mèo con này. Xin lưu ý rằng với sự sắp xếp này, những chú mèo con trở thành bạn mỗi ngày theo nhật ký của Asya đều ở trong các phòng liền kề.
| Đầu vào |
Đầu ra |
5
14
25
3 1
4 5 |
3 1 4 2 5 |