sport

Profesorul nostru de sport este bun prieten cu profesorul de matematică. Din acest motiv la ora de sport inventează tot felul de probleme şi apoi îi cere profesorului de matematică să le rezolve. Azi la ora de sport participă N elevi, care poartă tricouri cu numerele $1, 2, \dots, N$. La începutul orei, cei $N$ elevi se aşează în rând în ordinea $p_1, p_2, \dots p_N$ (adică elevul cu tricoul $p_1$ se aşează pe poziţia $1$ în rând, elevul cu tricoul $p_2$ stă pe poziţia $2$, etc., poziţiile în rând fiind numerotate de la $1$ la $N$ de la stânga la dreapta). Profesorul de sport spune aşa: "La comanda mea schimbaţi locurile astfel: pe poziţia $i$ să se aşeze elevul care acum stă pe poziţia $p_{p_i}$ (pentru fiecare $1 \leq i \leq N$)".

De exemplu, dacă $N=6$ şi iniţial elevii s-au aşezat astfel: $3, 1, 4, 2, 6, 5$

• După prima comandă: $4, 3, 2, 1, 5, 6$

Observaţi că pe poziţia $1$ se află elevul $3$ iar pe poziţia $3$ se află elevul $4$. După prima comandă pe poziţia $1$ va ajunge elevul $p_{p_1}=p_3=4$. Pe poziţia $2$ se află elevul $1$, iar pe poziţia $1$ se află elevul $3$. După prima comandă pe poziţia $2$ va ajunge elevul $p_{p_2}=p_1=3 \dots$

• După a doua comandă: $2, 4, 1, 3, 6, 5$.

Observaţi că în configuraţia obţinută după prima comandă pe poziţia $1$ stătea elevul $4$ deci după încă o comandă va ajunge pe poziţia $1$ elevul $p_4$, adică elevul 2. Pe poziţia $2$ stătea elevul $3$, deci după încă o comandă va ajunge pe poziţia 2 elevul $p_3$, adică elevul $4$ etc.

• După a treia comandă se obţine configuraţia $1, 2, 3, 4, 5, 6$.
• Iar după a patra comandă se revine la configuraţia iniţială.

Profesorul de sport îl întreabă pe profesorul de matematică: care este numărul minim de comenzi pe care trebuie să le dau astfel încât elevii să revină în configuraţia iniţială? Şi care ar fi cea mai mică configuraţie iniţială (considerând ordinea lexicografică) pentru care este necesar acelaşi număr minim de comenzi pentru a reveni la configuraţia iniţială.

Cerinţă

Scrieţi un program care să îl ajute pe profesorul de matematică să răspundă la cele două întrebări ale profesorului de sport.

Date de intrare

Fişierul de intrare sport.in conţine pe prima linie un număr natural $N$ reprezentând numărul de elevi. Pe cea de a doua linie se află $N$ valori distincte cuprinse între $1$ şi $N$ reprezentând configuraţia iniţială a elevilor.

Date de ieşire

Fişierul de ieşire sport.out va conţine două linii. Pe prima linie va fi scris un număr natural reprezentând numărul minim de comenzi ce trebuie date astfel încât elevii să revină la configuraţia iniţială. Pe cea de a doua linie vor fi scrise $N$ valori distincte cuprinse între $1$ şi $N$ reprezentând cea mai mică configuraţie iniţială (considerând ordinea lexicografică) pentru care este necesar acelaşi număr minim de comenzi pentru a reveni la configuraţia iniţială.

Restricții și precizări

• $1 \leq N \leq 500$
• Valorile scrise pe aceeaşi linie în fişierul de intrare, respectiv în fişierul de ieşire sunt separate prin spaţii.
• Spunem că o configuratie $p=(p_1, p_2, \dots, p_N)$ este mai mică din punct de vedere lexicografic decât o altă configuraţie $q=(q_1, q_2, \dots, q_N)$ dacă există un indice $k, 1 \leq k \leq N$ astfel încât $p_i=q_i$, pentru orice $1 \leq i \lt k$ şi $p_k \lt q_k$.
• Numărul minim de comenzi ce trebuie să fie efectuate este $\leq 2 \ 000 \ 000 \ 000$ (două miliarde).
• Se acordă $50$% din punctajul pe teste pentru prima cerinţă. Punctajul integral se acordă pentru rezolvarea ambelor cerinţe.

Exemplu

sport.in

6
3 1 4 2 6 5

sport.out

4
1 2 4 5 6 3