선수권 대회

시간 제한1초메모리 제한128 MB

요약

서로 지휘 관계가 없는 직원끼리 2인 팀을 만들 때 팀 수를 최대로 구합니다.

난이도: 어려움10점 중 8점
유형: 그리디, 트리, 힙, 정렬
정답자: 아직 제출이 없습니다

문제

어느 회사에는 상하 관계가 계층적으로 정해져 있습니다.

각 직원에게는 직속 상사가 최대 한 명 있습니다.
상사 관계는 추이적입니다. 즉, A가 B의 상사이고(직속일 필요는 없습니다) B가 C의 상사이면, A는 C의 상사입니다.
이 관계에는 순환이 없습니다. 즉, A가 B의 상사이면서 동시에 B가 A의 상사인 서로 다른 두 사람 A, B는 존재하지 않습니다.

회사는 직원 2명으로 이루어진 팀들이 겨루는 비치발리볼 선수권 대회를 열기로 했습니다. 직원들이 부담을 느끼지 않도록, 팀은 A가 B의 상사가 아니고 B도 A의 상사가 아닌 두 사람 (A, B)으로만 구성할 수 있습니다. 한 사람은 최대 한 팀에만 속할 수 있습니다.

대회에 출전할 수 있는 팀은 최대 몇 개입니까?

입력

첫째 줄에 테스트 케이스의 수 Z ( $1 \le Z \le 10$ )가 주어집니다.

각 테스트 케이스의 첫째 줄에는 직원 수 N ( $1 \le N \le 100000$ )이 주어집니다. 둘째 줄에는 N개의 정수 $a_1, a_2, \dots, a_N$ 이 주어지며, $a_i$ 는 $i$ 번 직원의 직속 상사 번호입니다 ( $1 \le a_i \le N$ ). $i$ 번 직원에게 상사가 없으면 $a_i = -1$ 입니다.

출력

각 테스트 케이스마다 대회에 출전할 수 있는 팀의 최대 개수를 한 줄에 하나씩 출력합니다.

예제7

예제 1
입력
```
2
6
-1 1 2 3 4 5
6
-1 -1 -1 1 4 5
```
예상 출력
```
0
2
```
예제 2
입력
```
1
1
-1
```
예상 출력
```
0
```
예제 3
입력
```
1
2
-1 -1
```
예상 출력
```
1
```
예제 4
입력
```
1
2
-1 1
```
예상 출력
```
0
```
예제 5
입력
```
1
5
-1 1 1 1 1
```
예상 출력
```
2
```
예제 6
입력
```
1
3
-1 1 1
```
예상 출력
```
1
```

예제 7

입력

3
4
-1 1 -1 3
1
-1
6
-1 -1 -1 -1 -1 -1

예상 출력

2
0
3