Son zamanlar, Sakurako bir permutasiyası tapıb.
O, bu permutasiyanın bütün xüsusiyyətlərini başa düşmək üçün, onu daha yaxşı araşdırmaq istəyir.
Bunu etmək üçün, onu maraqlı bir xüsusiyyətə malik permutasiya p_1p_2\dots p_k şəklində ifadə etməlidir:
p_i permutasiyasında, dəqiq iki indeks (a < b) var ki, p_{i}[a]\neq a və p_{i}[b]\neq b.
Həmçinin, əlavə bir xüsusiyyət olaraq: t[p_k[p_{k-1}[\dots[p_1[i]]\dots]]]=i.
Sizin tapşırığınız (k\le n-1) seçmək və p_1p_2\dots p_k permutasiyaları tapmaqdır. Əgər bir neçə cavab varsa, istənilənini çıxışa verə bilərsiniz.
a_1, a_2, \dots, a_n tam ədədlər ardıcıllığında əgər -dən -ə qədər hər bir tam ədədə dəqiq bir dəfə rast gəlinirsə o, permutasiya adlanır. Məsələn, [1, 5, 3, 4, 2] permutasiyadır. Lakin, [1, 3, 4] permutasiya deyil (burada -yə rast gəlinmir və -ə rast gəlinir, hansı ki, rast gəlinməməlidir) və [1, 2, 2, 3] də permutasiya deyil (burada -yə iki dəfə rast gəlinir və -ə rast gəlinmir).
Birinci sətirdə bir tam ədəd (2\le n\le 5 \cdot 10^5) — permutasiyasının uzunluğu verilir.
İkinci sətirdə sayda tam ədəd t_1, t_2, , t_n (1\le t_i \le n) — permutasiya verilir. -nin permutasiya olduğuna zəmanət verilir. Həmçinin, permutasiyasının ən az indeksi üçün t[x]\neq x (1\le x\le n) olduğuna zəmanət verilir.
Siz bir tam ədəd (1 \leq k\le n-1) çıxarmalısınız. Qeyd edək ki, -nı minimallaşdırmağa ehtiyac yoxdur.
Bundan sonra, seçdiyiniz permutasiyaları p_1, p_2, \dots, p_k çıxarmalısınız.
Çıxış çox böyük ola biləcəyindən, permutasiyaları tam çıxarmayacaqsınız. Bunun əvəzinə, hər permutasiya p_i üçün, p_{i}[q]\neq q olan bütün indekslərini çıxarmalısınız.
Example 1
Example 2
( bal): n\le 8;
( bal): n\le 100;
( bal): n \le 10^5;
( bal): əlavə məhdudiyyətlər olmadan.