| Fişierul intrare/ieşire: | arrows.in, arrows.out | Sursă | ad-hoc |
| Autor | Robert Varga | Adăugată de |  Ciprian Oprisa •cypry |
| Timp execuţie pe test | 1 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Arrows
Jocul Arrows se desfăşoară pe o tablă cu N căsuţe. Fiecare căsuţă este legată cu o săgeată de o altă căsuţă. Pornind de la o căsuţă putem urmări săgeţile să ajungem în altă căsuţa de oricâte ori.
Să se determine în câte moduri putem alege două căsuţe A şi B astfel încât putem ajunge de la A la B dar nu şi invers.
Date de intrare
Fişierul de intrare arrows.in conţine pe prima linie numărul de teste T. Fiecare test este format din două linii. Pe prima linie a fiecărui test se află numărul N, reprezentând numărul de căsuţe. Pe a doua linie a fiecărui test se află un şir de N numere A[i], separate prin câte un spaţiu, reprezentând pentru fiecare i = 1, 2, ..., N, căsuţa unde arată săgeata din căsuţa i.
Date de ieşire
În fişierul de ieşire arrows.out se va tipări câte o linie pentru fiecare test cu răspunsul la întrebare.
Restricţii
- 1 ≤ T ≤ 20
- 2 ≤ N ≤ 5*105
- 1 ≤ A[i] ≤ N
Exemplu
| arrows.in | arrows.out |
|---|---|
| 2 4 2 3 4 3 4 2 1 4 3 | 5 0 |
Explicaţie
În primul exemplu, căsuţa 1 conţine o săgeată spre căsuţa 2, căsuţa 2 spre căsuţa 3, căsuţa 3 spre căsuţa 4, iar căsuţa 4 spre căsuţa 3. Putem ajunge de la căsuţa 1 la oricare din căsuţele 2, 3 şi 4, fără ca din ele să putem ajunge la căsuţa 1. Deasemenea de la căsuţa 2 putem ajunge la căsuţele 3 şi 4 fără ca din căsuţele 3 şi 4 să putem ajunge la căsuţa 2. În schimb de la căsuţa 3 putem ajunge la 4 şi de la 4 la 3, deci această pereche nu trebuie numărată.
