Bài toán Tháp Hà Nội: Chuyển \(N\) đĩa từ cọc A sang cọc C dùng cọc trung gian \(B\) với số bước ít nhất.

Định dạng đầu vào

• Một dòng duy nhất chứa số nguyên dương \(N\) (\(1 \le N $\le 16\)).

Định dạng đầu ra

• Dòng đầu in ra số bước di chuyển tối thiểu \(2^N - 1\).
• Các dòng tiếp theo in ra từng bước di chuyển dạng u v (chuyển đĩa từ cọc \(u\) sang cọc \(v\)).

Ví dụ

Input:

2

Output:

3
1 2
1 3
2 3

Giải thích: Với 2 đĩa, cần 3 bước di chuyển: \(1 o 2\), \(1 o 3\), \(2 o 3\).

Ràng buộc & Subtasks