Nối các danh sách liên kết đôi

Danh sách liên kết đôi là một cấu trúc dữ liệu cơ bản: một dãy các phần tử, mỗi phần tử biết phần tử đứng trước và phần tử đứng sau nó trong danh sách. Trong bài này mọi danh sách đều có cấu trúc tuyến tính (không tạo thành chu trình): mỗi phần tử trừ phần tử đầu có đúng một phần tử liền trước, mỗi phần tử trừ phần tử cuối có đúng một phần tử liền sau.

Cho $N$ ô nhớ, đánh số từ $1$ đến $N$, tạo thành một hoặc nhiều danh sách liên kết đôi. Với mỗi ô $i$ cho hai giá trị:

• $l_i$ — ô chứa phần tử liền trước phần tử ở ô $i$;
• $r_i$ — ô chứa phần tử liền sau phần tử ở ô $i$.

Nếu phần tử ở ô $i$ không có phần tử liền trước thì $l_i=0$; nếu không có phần tử liền sau thì $r_i=0$.

Hãy nối tất cả các danh sách đã cho thành một danh sách duy nhất, ghép chúng lại với nhau theo thứ tự tùy ý. Nếu dữ liệu vào vốn đã là một danh sách duy nhất thì không cần làm gì cả.

Thao tác duy nhất được phép là nối đầu của một danh sách vào cuối của một danh sách khác — nghĩa là không được đảo ngược hay tách nhỏ các danh sách ban đầu; mọi liên kết bên trong mỗi danh sách ban đầu phải được giữ nguyên.

In ra danh sách kết quả dưới dạng các giá trị $l_i,r_i$. Nếu có nhiều đáp án hợp lệ, in ra bất kỳ đáp án nào.

Dữ liệu vào

• Dòng đầu chứa số nguyên $N$ — số ô nhớ.
• $N$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $l_i,r_i$.

Dữ liệu ra

In $N$ dòng, dòng thứ $i$ chứa hai số nguyên $l_i,r_i$ — ô liền trước và ô liền sau của ô $i$ sau khi đã nối tất cả các danh sách thành một danh sách duy nhất.

Ràng buộc

• $1\le N\le 100$
• $0\le l_i,r_i\le N$
• Dữ liệu vào luôn mô tả đúng một hoặc nhiều danh sách liên kết đôi có cấu trúc tuyến tính; mỗi ô nhớ chứa đúng một phần tử của một danh sách nào đó.

Ví dụ