Prologin, le concours national d'informatique

Énoncé¶

Malheureusement, Raphaël bloque son compte Netflux après trois tentatives échouées de connexion. Les 6 jeunes tentent alors d'aller directement voir le film au cinéma.

Cependant, ils ne savent pas qu'aujourd'hui, c'est la grève nationale de la Société Nationale des Cinémas Français ! Tous les cinémas sont donc fermés, mais chaque cinéma indique la position d'une autre salle de cinéma où aller en attendant la réouverture, qui est fermée à son tour...

Julie dirige la marche et doit prévoir les potentiels trajets.

$N$ cinémas sont numérotés par un nombre entre 1 et $N$. Tous les cinémas sont fermés, et la valeur redirection[i] donne le numéro du cinéma indiqué par le cinéma $i$.

Les jeunes commencent par aller voir le cinéma $S$. Voyant le cinéma fermé, ils vont donc vérifier le cinéma redirection[S], avant de constater que celui-ci est fermé aussi, et ainsi de suite.

Au bout d'un certain nombre de redirections, il est démontrable que les jeunes vont finir par retomber une 2e fois sur une salle de cinéma déjà visitée auparavant. À ce moment-là, ils s'arrêtent de parcourir les salles de cinéma, car ils savent qu'ils ne vont jamais en finir.

Aidez Julie à prédir, pour chaque valeur de $S$ (entre 1 et $N$), combien de salles de cinéma le groupe aurait visité ?

Entrée¶

L’entrée contiendra :

Sur la première ligne, un entier : N, le nombre de cinémas.
Sur la ligne suivante, une liste de N entiers séparés par des espaces : redirection, le lieu de redirection de chaque cinéma.

Sortie¶

Afficher, sur une ligne et séparé par un espace, le nombre de redirections nécessaires en partant de chaque cinéma avant de retomber à nouveau sur un cinéma déjà visité.

Attention à ne pas afficher d'espace terminal à la fin de la ligne.

Contraintes¶

$2 \le N \le 1\,000$
$1 \le redirection[i] \le N$
$redirection[i] \neq i$

Contraintes de performance¶

$2 \le N \le 100\,000$

Contraintes d'exécution

Utilisation mémoire maximum: 100000 kilo-octets
Temps d'exécution maximum: 1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée

4
3 1 4 1

Exemple de sortie

3 4 3 3

Commentaire

Si les jeunes commencent par la première salle de cinéma ($S = 1$), alors ils seront redirigés à la salle redirection[1] = 3, puis la salle redirection[3] = 4, et enfin redirection[4] = 1.

Au total, pour $S = 1$, ils auront visité les salles 1, 3 et 4, donc un total de 3 salles.

De manière similaire, voici le chemin suivi pour chaque point de départ :

S | Chemin
1 | 1 → 3 → 4 → 1
2 | 2 → 1 → 3 → 4 → 1
3 | 3 → 4 → 1 → 3
4 | 4 → 1 → 3 → 4

Ainsi, voici la liste des salles visitées pour chaque point de départ :

S | Salles visitées | Réponse
1 | 1, 3, 4         | 3
2 | 1, 2, 3, 4      | 4
3 | 1, 3, 4         | 3
4 | 1, 3, 4         | 3