Chuyển tháp đĩa theo quy tắc chuẩn

Bối cảnh và bài toán

Một hệ thống mô phỏng robot có ba cọc chứa các đĩa kích thước khác nhau. Ban đầu toàn bộ đĩa nằm ở cọc 1 theo thứ tự nhỏ trên, lớn dưới. Robot cần chuyển toàn bộ sang cọc 3; mỗi lần chỉ được chuyển đĩa trên cùng và không được đặt đĩa lớn lên đĩa nhỏ. Để hệ thống chấm được bằng output chuẩn, robot luôn dùng chiến lược đệ quy chuẩn: chuyển n-1 đĩa sang cọc trung gian, chuyển đĩa lớn nhất, rồi chuyển n-1 đĩa còn lại sang đích.

Yêu cầu

In số bước nhỏ nhất và chính xác chuỗi bước theo chiến lược đệ quy chuẩn mô tả ở trên.

Input

• Một dòng chứa số nguyên n.

Output

Dòng đầu in số bước. Mỗi dòng tiếp theo in hai số a b, nghĩa là chuyển đĩa trên cùng từ cọc a sang cọc b.

Ràng buộc

• 1 <= n <= 16

Chấm điểm

Ví dụ 1

Input

2

Output

3
1 2
1 3
2 3

Giải thích. Chuyển đĩa nhỏ sang cọc 2, đĩa lớn sang cọc 3, rồi đĩa nhỏ sang cọc 3.

Ví dụ 2

Input

1

Output

1
1 3

Giải thích. Chỉ có một đĩa nên cần đúng một lần chuyển.

Thông tin bài tập

Nguồn: Phỏng theo CSES Problem Set — Tower of Hanoi (Task 2165).

Tham khảo: https://cses.fi/problemset/task/2165/