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 :
Dans la permutation p_i, il y a exactement deux indices (a < b) tels que p_{i}[a]\neq a et p_{i}[b]\neq b.
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 ).
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)
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.
Example 1
Example 2
( points) : n\le 8 ;
( points) : n\le 100 ;
( points) : n \le 10^5 ;
( points) : sans contraintes supplémentaires.