Սակուրակո և տարօրինակPermutation#409

Սակուրակո և տարօրինակPermutation

1 վայրկյան
256 մեգաբայթ
Medium

Վերջերս, Սակուրակոն գտավ տեղափոխությունը:

Նա ցանկանում է ավելի լավ ուսումնասիրել այն, հասկանալու բոլոր նրա հատկությունները:

Այս նպատակով, նա պետք է ներկայացնի այն որպես հատ տեղափոխություններ՝ p_1p_2\dots p_k, հետաքրքիր հատկությամբ:

Եվ ևս մեկ հատկություն. 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]-ը նույնպես տեղափոխություն չէ (այն պարունակում է երկու հատ , և չի պարունակում ):

Input

Առաջին տողը պարունակում է մեկ ամբողջ (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)

Output

Դուք պետք է արտածեք (0 \leq k\le n-1) ամբողջ թիվը: Նշեք, որ -ն մինիմիզացնելու անհրաժեշտություն չկա:

Այնուհետև, դուք պետք է արտածեք հատ տեղափոխություններ՝ p_1, p_2, \dots, p_k, որոնք դուք ընտրել եք:

Քանի որ արտածումը կարող է շատ մեծ լինել, դուք չպետք է արտածեք տեղափոխություններն ամբողջությամբ: Փոխարենը, յուրաքանչյուր p_i տեղափոխության համար, դուք պետք է արտածեք բոլոր ինդեքսները, որտեղ p_{i}[q]\neq q:

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Scoring

  • ( միավոր): n\le 8;

  • ( միավոր): n\le 100;

  • ( միավոր): n \le 10^5;

  • ( միավոր): լրացուցիչ սահմանափակումներ չկան: