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, ..., N. La începutul orei, cei N elevi se aşează în rând în ordinea p[1] p[2] ... 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≤i≤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...
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 sport2.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 sport2.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
• 1 ≤ N ≤ 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, ..., p N) este mai mică din punct de vedere lexicografic decât o altă configuraţie q=(q1, q2, ..., qN) dacă există un indice k, 1≤k≤N astfel încât p i=qi, pentru orice 1≤i<k şi p k<qk.
• Numărul minim de comenzi ce trebuie să fie efectuate este ≤2000000000 (două miliarde).