De uno a ene (4) P44612

Statement

thehtml

Haced un programa que escriba las permutaciones de { 1, …, n } con un ciclo exactamente. Suponed que el contenido de la posición ‍i indica “la siguiente posición que hay que visitar”.

Por ejemplo, considerad la permutación (4,3,2,5,1,7,6). En la posición 1 hay un 4, en la posición 4 hay un 5, y en la 5 hay un 1. Así pues, uno de los ciclos de esta permutación es 1 → 4 → 5 → 1 (tiene dos ciclos más). En canvio, la permutación (3,4,5,6,7,1,2) sólo tiene un ciclo: 1 → 3 → 5 → 7 → 2 → 4 → 6 → 1.

Para hacer el problema más interesante, algunas posiciones ya estarán fijadas. Usaremos n ‍valores para indicarlo: las posiciones libres tendrán un 0, y las otras el valor ya fijado.

Entrada

La entrada consiste en un natural n > 0 seguido de los n valores para las posiciones fijadas.

Salida

Escribid todas las permutaciones de { 1, …, n } con un único ciclo que tienen las posiciones fijadas dadas. Siempre habrá al menos una solución.

Información sobre el corrector

Podéis escribir las soluciones de este ejercio en cualquier orden.

Public test cases

Input

1
0

Output

(1)

Input

3
0 0 0

Output

(2,3,1)
(3,1,2)

Input

6
4 0 6 0 0 0

Output

(4,3,6,2,1,5)
(4,5,6,2,3,1)
(4,5,6,3,1,2)
(4,1,6,3,2,5)
(4,3,6,5,2,1)
(4,1,6,5,3,2)

Input

7
3 4 0 6 0 1 2

Output

(3,4,5,6,7,1,2)

Information

Author: Salvador Roura
Language: Spanish
Translator: Salvador Roura
Original language: Catalan
Other languages: Catalan
Official solutions: C++
User solutions: C++