مؤخراً، وجدت ساكوراكوا تبديلة .
تريد أن تفحصها بشكل أفضل، لفهم جميع خصائصها.
للقيام بذلك، ستحتاج إلى تمثيلها كـ ترتيبات 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. من المضمون أن هو ترتيب. ومن المضمون أنه يوجد على الأقل مؤشرات من ترتيب 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;
( نقطة): بدون قيود إضافية.