Fişierul intrare/ieşire:	perm5.in, perm5.out	Sursă	Lot Suceava 2007
Autor	Emanuela Cerchez	Adăugată de	Bogdan-Cristian Tataroiu •bogdan2412
Timp execuţie pe test	0.025 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Perm 5

Fie N un numar natural si p = (p1, p2, ..., pN) o permutare de ordin N.
Numim grad al unei permutari cel mai mic numar natural k > 0, astfel incat

• p^k = popop...op (de k ori) = e

(unde cu e am notat permutare identica, deci permutarea pentru care e(i) = i, pentru orice i = 1, 2, ..., n).

Cerinta

Pentru un N dat, sa se determine o permutare de ordin N avand grad maxim. Daca exista mai multe solutii se va determina prima in ordine lexicografica.

Date de intrare

Fisierul de intrare perm5.in contine pe prima linie numarul natural nenul N.

Date de iesire

Fisierul de iesire perm5.out va contine o singura linie pe care vor fi scrise N numere naturale distincte cuprinse intre 1 si N, separate prin cate un spatiu, reprezentand prima permutare de grad maxim in ordine lexicografica.

Restrictii

• 1 ≤ N ≤ 2000
• Prin operatia o intelegem compunerea functiilor. Mai exact pop(i) = p(p(i)), pentru orice i = 1, 2, ..., N.

Exemplu

Explicatie

Permutarea (2, 1, 4, 5, 3) are gradul 6 (maxim posibil).
Exista si alte solutii, dar aceasta este cea mai mica din punct de vedere lexicografic.

Cum se trimit solutii?