ساكوراكوا وترتيب غريب#409

ساكوراكوا وترتيب غريب

ثانية
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. من المضمون أن هو ترتيب. ومن المضمون أنه يوجد على الأقل مؤشرات من ترتيب 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;

  • ( نقطة): بدون قيود إضافية.