题目描述

先给一个正整数$( 1 < = n < = 9 )$，输出所有全排列。 什么是全排列，例如$n＝3$，输出所有组合,并且按字典序输出： 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 每个全排列一行，相邻两个数用空格隔开（最后一个数后面没有空格）

输入格式

一行一个整数$n$。

输出格式

输出1~$n$的所有全排列。

样例 #1

样例输入 #1

3

样例输出 #1

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1