강강술래

강강술래는 추석(음력 8월 15일)에 여성들이 추던 한국의 전통 원무입니다. 여성들은 한복을 입고 넓은 마당에 모여 손을 맞잡고 원을 이루어 안쪽을 바라본 채, 노랫가락에 맞추어 천천히 원을 돌며 춤을 춥니다. 점점 빨라지다가 마지막에는 빙글빙글 도는 절정으로 춤이 끝납니다.

이 원무에 참여하고 싶은 소녀가 $N$명 있으며, $1$번부터 $N$번까지 번호가 매겨져 있습니다. 감독은 구성원 사이의 협동이 매우 중요한 춤 모임을 만들려고 합니다. 모든 소녀는 춤출 때 옆에 서고 싶은 소녀 한 명의 이름을 반드시 제출해야 하고, 원한다면 함께 춤추기 싫은 소녀 한 명의 이름을 추가로 제출할 수 있습니다.

감독은 이 명단을 보고 가장 큰 좋은 모임을 찾으려 합니다. 좋은 모임이란 다음 조건을 모두 만족하는 소녀의 집합 $S$입니다.

1. $S$에 속한 소녀는 $2$명 이상입니다.
2. $S$의 소녀들을 원형으로 $i_1, i_2, \dots, i_m$ ($m = |S|$)처럼 배열할 수 있어서, $i_1$은 $i_2$ 옆에, $i_2$는 $i_3$ 옆에, ..., $i_{m-1}$은 $i_m$ 옆에, 그리고 $i_m$은 $i_1$ 옆에 서고 싶어 합니다.
3. $S$의 모든 소녀에 대해, 그 소녀와 함께 춤추기 싫어하는 $S$ 안의 소녀 수가 $\lceil m/2 \rceil$보다 엄격하게 작습니다. (실수 $x$에 대해 $\lceil x \rceil$는 $x$ 이상인 가장 작은 정수입니다.)

예를 들어 소녀 $1$이 소녀 $2$ 옆에, 소녀 $2$가 소녀 $3$ 옆에, 소녀 $3$이 소녀 $4$ 옆에, 소녀 $4$가 소녀 $1$ 옆에, 소녀 $5$가 소녀 $6$ 옆에, 소녀 $6$이 소녀 $5$ 옆에 서고 싶어 한다고 합시다. 또한 소녀 $1$과 소녀 $2$가 소녀 $4$와 함께 춤추기 싫어한다고 합시다. 모임 $\{1, 2, 3, 4\}$는 조건 (1)과 (2)는 만족하지만 조건 (3)은 만족하지 않습니다. 소녀 $4$와 함께 춤추기 싫어하는 소녀가 두 명(소녀 $1$과 $2$)인데, 이는 $\lceil 4/2 \rceil = 2$보다 작지 않기 때문입니다. 따라서 가장 큰 좋은 모임은 $\{5, 6\}$입니다.

각 소녀가 제출한 명단이 주어질 때, 가장 큰 좋은 모임에 속한 소녀의 수를 구하는 프로그램을 작성하세요.

첫째 줄에 테스트 케이스의 수 $T$가 주어집니다.

각 테스트 케이스의 첫째 줄에는 소녀의 수 $N$ ($1 \le N \le 10{,}000$)이 주어집니다. 이어지는 $N$개의 줄 중 $i$번째 줄에는 두 정수 $j$와 $k$가 주어지며, $j$는 소녀 $i$가 옆에 서고 싶어 하는 소녀, $k$는 소녀 $i$가 함께 춤추기 싫어하는 소녀입니다. 소녀 $i$가 싫어하는 소녀를 제출하지 않았다면 $k$는 $-1$입니다.

각 테스트 케이스마다 가장 큰 좋은 모임에 속한 소녀의 수를 한 줄에 출력합니다. 좋은 모임이 없으면 $-1$을 출력합니다.