Programozás‎ > ‎Feladatok‎ > ‎

Örökre legjobb barátok

Tanár vagy a Kis Kódolók óvodában. Az csoportodba N gyermek jár, 1-től N-ig terjedő azonosítókkal számozva. Minden gyereknek van egyetlen Örökre Legjobb Barátja (ÖLeB), és tanárként ismered is ezeket a barátságokat. Az ÖLeB nem szimmetrikus, előfordulhat, hogy X örökre legjobb barátja Y, de Y-é nem X.

Meg kell tervezned egy olyan foglalkozást, ahol az óvodások körben ülve hajtanak végre egy feladatot. Tapasztalatból tudod, hogy a gyerekek jobban dolgoznak, ha örökre legjobb barátjuk mellett ülhetnek, ezért szeretnéd a lehető legnagyobb kört kialakítani, ahol mindenki az örökre legjobb barátja mellett ül. Az mindegy, hogy jobbra vagy balra ül a legjobb barát.

Előfordulhat, hogy nem tudod az összes gyereket leültetni a kör mentén, de szeretnéd a lehető legnagyobb kört kialakítani.

Feladat

Írjunk programot, ami megadja, hogy legfeljebb hány gyerek ültethető le egy kör mentén, a megadott feltételeknek megfelelően.

Bemenet

A bemenet első sora a tesztesetek T számát adja meg, 1 <= T <= 100. Ezután T teszteset következik. Minden teszteset első sora a diákok N számát adja meg, majd N diákazonosító következik: F1, F2, ..., Fn, ahol Fi az i. diák örökre legjobb barátjának azonosítója.

Kis tesztekre 3 <= N <= 10, nagyokra 3 <= N <= 1000. Feltehetjük, hogy Fi <> i, vagyis senki nem legjobb barátja önmagának.

Kimenet

Minden tesztesetre meg kell adni a kialakítható legnagyobb kör méretét.

Példa

Bemenet  Kimenet
4
4
2 3 4 1
4
3 3 4 1
4
3 3 4 3
10
7 8 10 10 9 2 9 6 3 3
Case #1: 4
Case #2: 3
Case #3: 3
Case #4: 6


Tesztadatok

Címkék

A feladat forrása: Google Code Jam 2016 Round 1A, https://code.google.com/codejam/contest/4304486/dashboard#s=p2
Algoritmusok: mélységi bejárás