Mô tả và yêu cầu

Có 3 cái cọc, đánh dấu 1, 2, 3, và N cái đĩa. Mỗi đĩa đều có một lỗ chính giữa để đặt xuyên qua cọc, các đĩa đều có kích thước khác nhau. Ban đầu tất cả đĩa đều được đặt ở cọc thứ nhất theo thứ tự đĩa nhỏ hơn ở trên.

Yêu cầu: Hãy viết chương trình chỉ ra cách chuyển tất cả các đĩa từ cọc 1 qua cọc 2 với ba ràng buộc như sau:
1. Mỗi lần chỉ chuyển được một đĩa.
2. Trong quá trình chuyển đĩa có thể dùng cọc còn lại (cọc 3) để làm cọc trung gian.
3. Chỉ cho phép đặt đĩa có bán kính nhỏ hơn lên đĩa có bán kính lớn hơn.

Dữ liệu vào

Từ thiết bị nhập chuẩn chứa một nguyên dương N là số cái đĩa.

Dữ liệu ra

Ghi ra màn hình gồm các dòng chứa cách thực hiện bài toán theo dạng x->y với ý nghĩa lấy đĩa ở cọc x (1 ≤ x ≤ 3) chuyển sang cọc y (1 ≤ y ≤ 3).

Ví dụ

3

1->2
1->3
2->3
1->2
3->1
3->2
1->2