Farmàcies italianes P92046

A l’últim SWERC de Milà, els equips UPC anaven amb esperances de classificar-se per a la final mundial. Per evitar-ho, els malvats equips de l’EP (Estudiants Parisencs) i de l’ETH (Estudiants Teòricament Helvètics, però amb xinesos), van pressionar els seus contactes del govern italià per canviar la política anti-COVID, fent que els certificats de vacunació d’en Nistal i en Conchello ja no fossin vàlids.

Sense aquests certificats, l’equip UPC-2 no podia participar al concurs. L’única manera d’arreglar-ho era fer-se una prova COVID. Així doncs, l’equip UPC es va dirigir a la farmàcia més propera (que anomenarem farmàcia 1) a demanar si allà feien aquestes proves. A la farmàcia 1 els van dir que allà no en feien, i que havien d’anar a la farmàcia 2. A la farmàcia ‍2 els van dir que allà tampoc, i que havien d’anar a la farmàcia 3. I a la farmàcia ‍3 els van dir que allà tampoc, i que anessin a la farmàcia 1. Malauradament, l’equip UPC havia quedat atrapat en un cicle de farmàcies, del qual potser ja mai podrien sortir. Mentre la resta de l’equip pensava què podien fer, l’Izan es va posar a pensar en el problema següent:

Suposem que tenim n farmàcies numerades entre 1 i n. Per a cada farmàcia i, sabem el número de la farmàcia a la qual es redirigeixen els clients. Quina és la longitud del cicle més llarg de farmàcies en que algú es pot quedar atrapat?

Entrada

L’entrada conté diversos casos, cadascun amb n, seguida d’una permutació de {1, …, n}. Podeu suposar 1 ≤ n ≤ 10⁴.

Sortida

Per a cada cas, escriviu la longitud del cicle més llarg.