Asya và Mèo Con

Có $n$ chú mèo con đánh số từ $1$ đến $n$, ban đầu được đặt vào một dãy $n$ ô chuồng đánh số từ $1$ đến $n$ (mỗi ô chứa đúng một chú mèo, các ô liền kề ban đầu được ngăn bởi vách).

Trong $n-1$ ngày liên tiếp, có một cặp mèo $(x_i,y_i)$ ở hai ô liền kề muốn chơi cùng nhau, và vách giữa hai ô đó bị gỡ bỏ — gộp hai ô (cùng toàn bộ mèo trong chúng) thành một ô lớn. Sau $n-1$ ngày, toàn bộ mèo nằm trong một ô duy nhất.

Cho biết các cặp $(x_i,y_i)$ theo thứ tự ngày, hãy in ra một cách xếp ban đầu các chú mèo vào $n$ ô sao cho mọi ngày, hai chú mèo $x_i$ và $y_i$ thực sự nằm trong hai ô liền kề (sau khi đã gộp các ô từ các ngày trước).

Nếu có nhiều đáp án, in ra bất kỳ đáp án nào.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $n$.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_i$, $y_i$ — chỉ số của hai chú mèo gộp ô trong ngày $i$. Đảm bảo $x_i\ne y_i$ và trước ngày $i$, hai chú mèo nằm trong hai ô khác nhau.

Dữ liệu ra

In ra $n$ số nguyên phân biệt thuộc $\{1,\dots ,n\}$ trên cùng một dòng, cách nhau bởi dấu cách: số thứ $j$ là chỉ số của chú mèo ban đầu ở ô thứ $j$.

Bài có nhiều đáp án; bộ chấm sẽ kiểm tra đáp án của bạn có thoả mãn yêu cầu hay không.

Ràng buộc

• $2\le n\le 150000$
• $1\le x_i,y_i\le n$, $x_i\ne y_i$
• Đảm bảo tồn tại ít nhất một cách xếp hợp lệ.

Ví dụ