Permutacions xules P51435

Statement

En aquest problema, direm que una permutació és xula si no té dos nombre consecutius seguits. Donada una $n$ , escriviu totes les permutacions xules de $\{0, \dots, n - 1\}$ .

Entrada

L’entrada consisteix en diversos casos, cadascun amb una $n$ entre 1 i 9.

Sortida

Per a cada cas, escriviu en ordre lexicogràfic totes les permutacions xules de $\{0, \dots, n - 1\}$ . Escriviu una línia amb 20 asteriscs al final de cada cas.

Public test cases

Input

Output

0
********************
********************
********************
1 3 0 2
2 0 3 1
********************
0 2 4 1 3
0 3 1 4 2
1 3 0 2 4
1 3 0 4 2
1 4 2 0 3
2 0 3 1 4
2 0 4 1 3
2 4 0 3 1
2 4 1 3 0
3 0 2 4 1
3 1 4 0 2
3 1 4 2 0
4 1 3 0 2
4 2 0 3 1
********************

Information

Author: Salvador Roura
Language: Catalan
Other languages: English
Official solutions: C++
User solutions: C++ Python