Sakurako et une permutation étrange#409

Sakurako et une permutation étrange

1 seconde
256 mégaoctets
Medium

Récemment, Sakurako a trouvé une permutation .

Elle souhaite l'examiner de plus près, pour comprendre toutes ses propriétés.

Pour ce faire, elle devra la représenter sous la forme de permutations p_1p_2\dots p_k avec une propriété intéressante :

De plus, comme propriété supplémentaire : t[p_k[p_{k-1}[\dots[p_1[i]]\dots]]]=i.

Votre tâche est de choisir (k\le n-1) et de trouver les permutations p_1p_2\dots p_k. S'il y a plusieurs réponses, vous pouvez en fournir n'importe quelle.

Une séquence d'entiers a_1, a_2, \dots, a_n est appelée une permutation si la séquence contient chaque entier de à exactement une fois. Par exemple, [1, 5, 3, 4, 2] est une permutation. Cependant, [1, 3, 4] n'est pas une permutation (elle ne contient pas et contient , qui ne devrait pas apparaître dans la séquence), et [1, 2, 2, 3] n'est pas une permutation non plus (elle contient deux fois et ne contient pas ).

Input

La première ligne contient un entier (2\le n\le 5 \cdot 10^5) — la longueur de la permutation .

La deuxième ligne contient entiers t_1, t_2, , t_n (1\le t_i \le n) — la permutation. Il est garanti que est une permutation. Il est garanti que pour au moins indices de la permutation t[x]\neq x. (1\le x\le n)

Output

Vous devez afficher un entier (0 \leq k\le n-1). Notez qu'il n'est pas nécessaire de minimiser .

Après cela, vous devez afficher permutations p_1, p_2, \dots, p_k que vous avez choisies.

Comme la sortie peut devenir énorme, vous ne sortirez pas les permutations en entier. Au lieu de cela, pour chaque permutation p_i, vous devez afficher tous les indices pour lesquels p_{i}[q]\neq q.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Scoring

  • ( points) : n\le 8 ;

  • ( points) : n\le 100 ;

  • ( points) : n \le 10^5 ;

  • ( points) : sans contraintes supplémentaires.