Búsqueda de un ciclo en una permutación con suma máxima

Python Hard loops

Tarea «Búsqueda de un ciclo en una permutación con suma máxima»

Dada una permutación de números del 1 al N. Considere un grafo dirigido donde cada vértice i tiene una arista hacia a[i]. Encuentre un ciclo en este grafo cuya suma de elementos sea máxima. Si hay varios ciclos de este tipo, muestre cualquiera. Se garantiza que N ≥ 2. Se considera ciclo a una secuencia de vértices distintos donde cada vértice siguiente se obtiene según la regla: siguiente = a[actual], y el último vértice regresa al primero mediante una arista.

Formato de entrada

La primera línea contiene un número entero N (2 ≤ N ≤ 10^5). La segunda línea contiene N números enteros a[1], a[2], ..., a[N] — una permutación de los números del 1 al N.

Formato de salida

Muestre dos números: la longitud del ciclo y la suma de los elementos del ciclo. Luego, en la siguiente línea, muestre los elementos del ciclo en orden de recorrido, comenzando desde cualquier elemento.

Ejemplos

Ejemplo 1

ENTRADA

5
2 3 1 5 4

SALIDA

2 9
4 5

Ejemplo 2

ENTRADA

7
1 2 3 4 5 6 7

SALIDA

1 7
7

Ejemplo 3

ENTRADA

4
abc
cde
xyz
zab

SALIDA

Invalid input

Ejemplo 4

ENTRADA

4
2 1 4 3

SALIDA

2 7
3 4

Ejemplo 5

ENTRADA

3
1 0 2

SALIDA

1 1
1

main.py