📖 Bài giảng & lời giải: đây là Bài tập 1 trong bài giảng Thuật toán qua trò chơi 1: Tháp Hà Nội trên blog Lập trình thuật toán – có lý thuyết, mô phỏng từng bước, gợi ý và code C++ / Python.

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới xem gợi ý và lời giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Trò chơi Tháp Hà Nội: có 3 cột đánh số 1, 2, 3 và $n$ đĩa có kích thước khác nhau. Ban đầu cả $n$ đĩa nằm ở cột 1, đĩa lớn ở dưới, đĩa nhỏ ở trên. Mỗi nước đi được lấy một đĩa trên cùng của một cột đặt lên đỉnh một cột khác, và không bao giờ được đặt đĩa lớn lên trên đĩa nhỏ hơn.

Hãy chuyển cả tháp sang cột 3 với số nước ít nhất. (Có thể chứng minh cách chuyển với số nước ít nhất là duy nhất.)

Dữ liệu vào

Một số nguyên $n$ ($1 \le n \le 16$).

Kết quả

• Dòng đầu tiên in số nước ít nhất $m$.
• $m$ dòng tiếp theo, dòng thứ $i$ gồm hai số $x\ y$ cách nhau một dấu cách, nghĩa là ở nước thứ $i$ ta lấy đĩa trên cùng của cột $x$ đặt lên cột $y$.

Sample Input

2

Sample Output

3
1 2
1 3
2 3