Giáo sư Taylor Swift đang chấm bài tập về skew heap số nguyên. Một skew heap là một cây nhị phân trong đó mỗi nút lưu trữ một số nguyên sao cho giá trị tại bất kỳ nút nào cũng nhỏ hơn hoặc bằng giá trị các nút con của nó. Lưu ý rằng skew heap không nhất thiết phải là một cây nhị phân hoàn hảo; nghĩa là cây con bên trái và/hoặc bên phải của bất kỳ nút nào cũng có thể trống.

Việc chèn một giá trị \(x\) vào một skew heap \(H\) được thực hiện theo quy trình đệ quy sau:

• Nếu \(H\) trống, tạo \(H\) thành một skew heap chỉ gồm một nút duy nhất chứa giá trị \(x\).
• Ngược lại, gọi \(y\) là giá trị ở gốc của \(H\):
  • Nếu \(y < x\): Tráo đổi (swap) hai cây con của gốc và chèn \(x\) một cách đệ quy vào cây con bên trái mới.
  • Nếu \(y \geq x\): Tạo một nút mới với giá trị \(x\) và đặt \(H\) làm cây con bên trái của nút mới này.

Bà tự hỏi rằng: Với một cấu trúc cây cho trước, liệu có tồn tại một hoán vị đầu vào nào của các số từ \(1\) đến \(n\) (được chèn theo thứ tự vào heap trống) để tạo ra cây đó hay không? Nếu có, hãy tìm hoán vị nhỏ nhất và lớn nhất về mặt từ điển.

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 2 \cdot 10^5\)), là số lượng nút trong cây. Các nút này chứa chính xác các số từ \(1\) đến \(n\).
• Tiếp theo là \(n\) dòng, dòng thứ \(i\) chứa hai số nguyên \(\ell_i\) và \(r_i\) (\(i < \ell_i \le n\) hoặc \(\ell_i = 0\); \(i < r_i \le n\) hoặc \(r_i = 0\)), mô tả giá trị của con trái và con phải của nút lưu trữ giá trị \(i\).
• Giá trị \(0\) biểu thị con tương ứng không tồn tại. Dữ liệu đảm bảo cấu trúc mô tả là một cây nhị phân.

Output

• Nếu không tồn tại hoán vị nào tạo ra cây đã cho, in ra impossible.
• Ngược lại, in ra hai dòng:
  • Dòng 1: Hoán vị nhỏ nhất về mặt từ điển.
  • Dòng 2: Hoán vị lớn nhất về mặt từ điển.
  • Nếu hai hoán vị này giống nhau, bạn vẫn phải in cả hai dòng.

Example

7
2 3
4 5
6 7
0 0
0 0
0 0
0 0

1 3 2 7 5 6 4
7 1 5 3 2 6 4

2
0 2
0 0

impossible

3
2 0
3 0
0 0

2 3 1
3 2 1