Busca de ciclo em permutação com soma máxima

Python Hard loops

Tarefa «Busca de ciclo em permutação com soma máxima»

Dada uma permutação dos números de 1 a N. Considere um grafo direcionado onde cada vértice i possui uma aresta para a[i]. Encontre um ciclo nesse grafo cuja soma dos elementos seja máxima. Se houver múltiplos ciclos, imprima qualquer um. É garantido que N ≥ 2. Um ciclo é definido como uma sequência de vértices distintos, onde cada vértice seguinte é obtido pela regra: próximo = a[atual], e o último vértice retorna ao primeiro por uma aresta.

Formato de Entrada

A primeira linha contém um número inteiro N (2 ≤ N ≤ 10^5). A segunda linha contém N números inteiros a[1], a[2], ..., a[N] — uma permutação dos números de 1 a N.

Formato de Saída

Imprima dois números: o comprimento do ciclo e a soma dos elementos do ciclo. Em seguida, na próxima linha, imprima os elementos do ciclo na ordem de percurso, começando por qualquer elemento.

Exemplos

Exemplo 1

ENTRADA

5
2 3 1 5 4

SAÍDA

2 9
4 5

Exemplo 2

ENTRADA

7
1 2 3 4 5 6 7

SAÍDA

1 7
7

Exemplo 3

ENTRADA

4
abc
cde
xyz
zab

SAÍDA

Invalid input

Exemplo 4

ENTRADA

4
2 1 4 3

SAÍDA

2 7
3 4

Exemplo 5

ENTRADA

3
1 0 2

SAÍDA

1 1
1

main.py