Masala #0442

Xotira 16 MB Vaqt 1000 ms Qiyinchiligi 40 %
14

  

Oppog’oydan xat

Oppog’oy va 7 gnom ertagi barchangizga tanish bo’lsa kerak.

Endi ertakni biroz o’zgartiramiz gnomlar soni \(N\) ta bo’lib har birining isimlari 1 dan \(N\) gacha raqamlangan. Ular ertalab tongda uyg’onib ishga ketishadi va kech kirganda uyga qaytishadi. Kunlardan bir kun ular kech kirganida uyiga qaytishsa ularga Oppog’oydan xatlar kelganini kurishdi, xatlar jami \(N\) ta bo’lib 1 dan \(N\) gacha raqamalangan. Gnomlar xatlar raqamlanganini bilmagan holda istalgan bir xatni olishdi ya’ni \(i\)-chi gnom \(a[i]\) raqamli xatni olishdi, aslida i-chi gnom olgan xat \(a[i]\)-chi raqamli ginomga tegishli edi. Endi gnomlar xatlarni bir biri bilan almashgan holda ismi bilan bir xil bo’lgan xatni topmoqchi.

Almashinish \(i\)-chi gnom uchun quyidagicha amalga oshiriladi.

  • \(i\)-chi gnom \(a[i]\) isimli gnom bilan xatlarni almashadi.
  • \(i = a[i]\) teng bo’lganida almashini to’xtadi.

Sizning vazifangiz har bir ginom uchun o’zining ismi bilan bir xil bo’lgan xatni topguncha nechchi marotaba xat almashinish kerak ekanligini aniqlashdan iborat.


Kiruvchi ma'lumotlar:

Kirish fayilining birinchi satrida \(N ( 1 \le N \le 10^6)\) soni jami gnomlar sonini ifodalaydi. Ikkinchi satrida \(N\) ta son \(i\)-chi gnom dastlab olgan \(a_i (1 \le a_i \le N)\) raqamli xat.


Chiquvchi ma'lumotlar:

Har bir gnom uchun o’zining xatini qo’lga kiritguncha almashinishlar sonini bitta satrida probel bilan ajratilgan holda chop eting.


Misollar
# input.txt output.txt
1
3
2 1 3
1 1 0
2
6
4 6 2 1 5 3
1 2 2 1 0 2
Izoh:

Izoh: 2-test uchun 4 6 2 1 5 3

  • 1-gnom 4-chi gnom bilan xatlarni almashadi 1 6 2 4 5 3 jami 1 ta
  • 2-gnom 6-chi gnom bilan xatlarni almashadi 4 3 2 1 5 6
  • 2-gnom 3-chi gnom bilan xatlarni almashadi 4 2 3 1 5 6 jami 2 ta
  • .....
  • 6-gnom 3-chi gnom bilan xatlarni almashadi 4 6 3 1 5 2
  • 6-gnom 2-chi gnom bilan xatlarni almashadi 4 2 3 1 5 6 jami 2 ta
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin