THỰC HÀNH

Cho tập hợp A = {1, 2, …, n}. Liệt kê các hoán vị của A.

Dữ liệu vào:

Một  dòng duy nhất chứa số nguyên dương n

Dữ liệu ra:

Gồm nhiều dòng, mỗi dòng là một hoán vị của tập A, các hoán vị liệt kê theo thứ tự từ điển tăng dần, mỗi số trên một dòng cách nhau bởi một dấu cách.

Ví dụ:

Dữ liệu vào:
3

Dữ liệu ra:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Giải thích: Tập A có 3 phần tử thì sẽ có 6 hoán vị, các hoán vị được liệt kê theo thứ tự tăng dần như trên.

Giới hạn: 1 ≤ n ≤ 9.