Jeon Dae-Pyeon từng tuyên bố sẽ chuyển UCPC sang thể thức thi đấu loại trực tiếp từ 3 năm trước, nhưng họ đã gặp phải nhiều khó khăn do thực hiện thay đổi quá lớn. Năm nay, Hye-ah, chủ tịch của Jeon Dae-Pyeon, đã tìm thấy các tài liệu chuẩn bị cho giải đấu này khi đọc lại các văn bản nội bộ và quyết định tổ chức lại giải đấu theo thể thức loại trực tiếp.

May mắn thay, vì UCPC lần này có chính xác $2^N$ người tham gia, Hye-ah có thể tổ chức giải đấu một cách rất gọn gàng theo thể thức loại trực tiếp đơn (single elimination). Đây là thể thức thi đấu mà mọi người thường nghĩ đến đầu tiên khi nhắc đến "giải đấu", và quy trình cụ thể như sau:

1. Gán cho mỗi người tham gia một số hạt giống khác nhau từ $1$ đến $2^N$, sau đó xếp họ thành một hàng theo thứ tự bất kỳ.
2. Ghép cặp các người tham gia trong hàng theo từng đôi một từ đầu hàng. Hai người được ghép cặp sẽ thi đấu với nhau, và người thua cuộc sẽ rời khỏi hàng. Sau khi tất cả các cặp đã thi đấu xong, số người còn lại trong hàng sẽ giảm đi một nửa so với ban đầu.
3. Do đó, nếu lặp lại quy trình 2 đúng $N$ lần, chỉ còn lại duy nhất một người tham gia, và người này trở thành nhà vô địch của giải đấu.

Giải đấu loại trực tiếp đơn thường được biểu diễn bằng sơ đồ thi đấu dạng cây nhị phân như dưới đây.

Hình K.1: Ví dụ về sơ đồ thi đấu của một giải đấu với $2^3 = 8$ người tham gia

Ban tổ chức giải đấu, bao gồm cả Hye-ah, đã giám sát tất cả các trận đấu diễn ra và ghi lại kết quả vào một tài liệu chung. Tuy nhiên, vì có nhiều người cùng ghi kết quả vào tài liệu một cách lộn xộn, nên không thể hiểu được diễn biến của giải đấu từ bản ghi này. Hơn nữa, sau khi giải đấu kết thúc, ban tổ chức đã đếm số lượng trận đấu và phát hiện ra một sự thật đáng buồn là một trận đấu đã bị bỏ sót.

Thay cho ban tổ chức đã quá mệt mỏi vì điều hành giải đấu và không còn sức lực để giải quyết tình trạng này, hãy tìm ra trận đấu bị thiếu trong bản ghi.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $N$ ($2 \le N \le 20$).

Trên $2^N - 2$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_i$ và $b_i$ cách nhau bởi dấu cách, biểu thị kết quả của mỗi trận đấu. Điều này có nghĩa là trong trận đấu, người tham gia số $a_i$ đã đấu với người tham gia số $b_i$ và người tham gia số $a_i$ đã thắng.

Dữ liệu đầu vào được đảm bảo là một bản ghi đầy đủ của giải đấu nhưng bị thiếu mất một trận đấu. Nói cách khác, không có trường hợp nào mà dù có suy đoán kết quả của trận đấu bị thiếu như thế nào đi nữa thì cũng không thể tạo ra một bản ghi hợp lệ.

Dữ liệu ra

In ra kết quả của trận đấu bị thiếu dưới dạng hai số nguyên theo cùng định dạng với dữ liệu vào. Nếu có nhiều kết quả trận đấu khả thi, hãy in ra tất cả các đáp án khả thi, mỗi đáp án trên một dòng. Khi đó, hãy sắp xếp theo thứ tự số của người thắng nhỏ trước, nếu có nhiều trường hợp như vậy thì sắp xếp theo số của người thua nhỏ trước.

Ví dụ

Ví dụ 1

3
3 6
1 8
3 7
3 5
6 1
7 4

6 2

Ví dụ 2

2
3 4
1 2

1 3
3 1

Ghi chú

Sơ đồ thi đấu của ví dụ đầu tiên giống với hình vẽ được cung cấp trong đề bài.

Ví dụ thứ hai là bản ghi của một giải đấu với $2^2 = 4$ người tham gia nhưng bị thiếu trận chung kết. Vì không thể biết ai là người thắng cuộc trong trận chung kết, nên hãy in ra cả hai khả năng.