‹ 上一题下一题 ›

j01981. 错位排列全输出未做

1000 ms 256 MB 测试点 10 通过率 100% 搜索 J·复赛必做100题自拟题 r2 深度优先搜索

文件读写输入j01981.in输出j01981.out

题目描述

输入 $n$ ，按字典序输出 $1 \sim n$ 的所有错位排列（没有任何 $i$ 恰好排在第 $i$ 位的排列），每行一个，数字间空格分隔；最后一行输出排列总数。

输入格式

一行一个整数 $n$ 。

输出格式

共若干行排列，最后一行为总数。

样例

输入

输出

2 3 1
3 1 2
2

数据范围

对于 30% 的数据， $n \leq 4$ （先全枚举再过滤可过）。
对于 60% 的数据， $n \leq 6$ 。
对于 100% 的数据， $1 \leq n \leq 7$ 。

输入

输出

答案