Dây đèn tự chế

Một dây đèn trang trí gồm $n$ bóng đèn (đánh số từ $1$ đến $n$) và $n-1$ sợi dây nối. Đúng một bóng đèn được nối trực tiếp với nguồn điện, và điện được truyền từ bóng này tới các bóng còn lại thông qua các sợi dây. Mỗi sợi dây nối đúng hai bóng đèn: một bóng gọi là bóng chính của sợi dây (bóng nhận điện từ phía nguồn rồi truyền tiếp qua sợi dây này), bóng còn lại gọi là bóng phụ (bóng nhận điện qua chính sợi dây này). Như vậy cấu trúc của dây đèn là một cây có gốc, gốc là bóng nối với nguồn.

Bóng đèn thứ $i$ có độ sáng bằng $2^i$. Với mỗi sợi dây, ta định nghĩa độ quan trọng của nó là tổng độ sáng của tất cả các bóng đèn bị mất điện nếu cắt sợi dây đó đi (các sợi dây khác vẫn hoạt động bình thường) — tức là tổng $2^i$ trên toàn bộ cây con nằm phía dưới sợi dây (phía bóng phụ).

Vì mọi độ sáng đều là các lũy thừa khác nhau của $2$, nên độ quan trọng của $n-1$ sợi dây là đôi một khác nhau. Người ta đánh số các sợi dây từ $1$ đến $n-1$ theo thứ tự giảm dần của độ quan trọng, rồi ghi lại chỉ số bóng chính của từng sợi dây theo đúng thứ tự đó, thu được dãy $a_1,a_2,\dots ,a_{n-1}$.

Cho dãy $a$, hãy khôi phục lại một sơ đồ dây đèn phù hợp. Dữ liệu luôn đảm bảo tồn tại ít nhất một sơ đồ hợp lệ; nếu có nhiều sơ đồ thỏa mãn, in ra một sơ đồ bất kỳ.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — số bóng đèn.
• Dòng thứ hai chứa $n-1$ số nguyên $a_1,a_2,\dots ,a_{n-1}$, trong đó $a_i$ là chỉ số bóng chính của sợi dây thứ $i$ (các sợi dây được đánh số theo thứ tự giảm dần của độ quan trọng).

Dữ liệu ra

• Dòng đầu in ra một số nguyên $k$ — chỉ số bóng đèn được nối với nguồn điện (gốc của cây).
• Tiếp theo in ra $n-1$ dòng, mỗi dòng gồm hai số nguyên $x_i$ và $y_i$ ($x_i\ne y_i$) — hai bóng đèn được nối bởi một sợi dây. Các sợi dây (và hai đầu của mỗi sợi dây) có thể in theo thứ tự bất kỳ.

Sơ đồ in ra phải là một sơ đồ dây đèn mà từ đó có thể ghi được đúng dãy $a_1,a_2,\dots ,a_{n-1}$.

Ràng buộc

• $2\le n\le 2·{10}^5$
• $1\le a_i\le n$

Ví dụ