Problem 2339: perm

Fie $n$ un număr natural şi $p=(p_1, p_2, \dots, p_n)$ o permutare de ordin $n$ . Numim grad al unei permutări cel mai mic număr natural $k>0$ , astfel încât $p^k = p \circ p \circ p \circ \dots \circ p = e$ (de $k$ ori), unde cu $e$ am notat permutare identică, deci permutarea pentru care $e(i)=i$ , pentru orice $i=1, 2, \dots, n$ .

Cerință

Pentru un $n$ dat, să se determine o permutare de ordin $n$ având grad maxim. Dacă există mai multe soluţii se va determina prima în ordine lexicografică.

Date de intrare

Fişierul de intrare perm.in conţine pe prima linie numărul natural nenul $n$ .

Date de ieșire

Fişierul de ieşire perm.out va conţine o singură linie pe care vor fi scrise $n$ numere naturale distincte cuprinse între $1$ şi $n$ , separate prin câte un spaţiu, reprezentând prima permutare de grad maxim în ordine lexicografică.

Restricții și precizări

$1 \leq N \leq 2 \ 000$ ;
Prin operaţia $\circ$ înţelegem compunerea funcţiilor. Mai exact $p \circ p(i) = p(p(i))$ , pentru orice $i=1, 2, \dots, n$ .

Exemplul 1

perm.in

perm.out

2 1 4 5 3

Explicație

Permutarea $(2, 1, 4, 5, 3)$ are gradul $6$ (maxim posibil). Există şi alte soluţii, dar aceasta este cea mai mică din punct de vedere lexicografic.

Exemplul 2