Վերջերս, Սակուրակոն գտավ տեղափոխությունը:
Նա ցանկանում է ավելի լավ ուսումնասիրել այն, հասկանալու բոլոր նրա հատկությունները:
Այս նպատակով, նա պետք է ներկայացնի այն որպես հատ տեղափոխություններ՝ p_1p_2\dots p_k, հետաքրքիր հատկությամբ:
p_i տեղափոխությունում կան ճիշտ երկու ինդեքսներ՝ (a < b) այնպես, որ p_{i}[a]\neq a և p_{i}[b]\neq b:
Եվ ևս մեկ հատկություն. t[p_k[p_{k-1}[\dots[p_1[i]]\dots]]]=i:
Ձեր առաջադրանքն է ընտրել (k\le n-1) և գտնել p_1p_2\dots p_k տեղափոխությունները։ Եթե կան մի քանի պատասխաններ, կարող եք արտածել ցանկացածը։
Թվերի a_1, a_2, \dots, a_n հաջորդականությունը կոչվում է տեղափոխություն, եթե հաջորդականությունը պարունակում է -ից թվերի յուրաքանչյուրը ճիշտ մեկ անգամ։ Օրինակ, [1, 5, 3, 4, 2]-ը տեղափոխություն է։ Սակայն, [1, 3, 4]-ը տեղափոխություն չէ (այն չի պարունակում և պարունակում է , որը չպետք է լինի հաջորդականությունում), և [1, 2, 2, 3]-ը նույնպես տեղափոխություն չէ (այն պարունակում է երկու հատ , և չի պարունակում ):
Առաջին տողը պարունակում է մեկ ամբողջ (2\le n\le 5 \cdot 10^5) թիվ՝ տեղափոխության երկարությունը:
Երկրորդ տողը պարունակում է ամբողջ թվեր t_1, t_2, , t_n (1\le t_i \le n) — տեղափոխությունը: Երաշխավորվում է, որ -ն տեղափոխության է: Երաշխավորվում է, որ տեղափոխության առնվազն ինդեքսների համար t[x]\neq x : (1\le x\le n)
Դուք պետք է արտածեք (0 \leq k\le n-1) ամբողջ թիվը: Նշեք, որ -ն մինիմիզացնելու անհրաժեշտություն չկա:
Այնուհետև, դուք պետք է արտածեք հատ տեղափոխություններ՝ p_1, p_2, \dots, p_k, որոնք դուք ընտրել եք:
Քանի որ արտածումը կարող է շատ մեծ լինել, դուք չպետք է արտածեք տեղափոխություններն ամբողջությամբ: Փոխարենը, յուրաքանչյուր p_i տեղափոխության համար, դուք պետք է արտածեք բոլոր ինդեքսները, որտեղ p_{i}[q]\neq q:
Example 1
Example 2
( միավոր): n\le 8;
( միավոր): n\le 100;
( միավոր): n \le 10^5;
( միավոր): լրացուցիչ սահմանափակումներ չկան: