Circle Dance

Ganggangsullae is a Korean circle dance traditionally performed by women during Chuseok, the harvest festival held on the fifteenth day of the eighth lunar month. Wearing the traditional dress called hanbok, the women gather in an open field, join hands in a circle facing the center, and move slowly around to the rhythm of a song. The pace gradually quickens until the dance ends in a whirling climax.

There are $N$ girls who want to take part in this circle dance, numbered from $1$ to $N$. A director wants to form a group for the dance in which cooperation among the members matters a great deal. Every girl must name exactly one girl she wants to stand next to while dancing, and she may optionally name one girl she does not want to dance with.

From these lists, the director looks for the largest good group. A good group is a set $S$ of girls that satisfies all of the following conditions:

1. $S$ contains at least $2$ girls.
2. The girls of $S$ can be arranged in a circle $i_1, i_2, \dots, i_m$ (where $m = |S|$) such that $i_1$ wants to stand next to $i_2$, $i_2$ wants to stand next to $i_3$, ..., $i_{m-1}$ wants to stand next to $i_m$, and $i_m$ wants to stand next to $i_1$.
3. For every girl in $S$, the number of girls in $S$ who do not want to dance with her is strictly less than $\lceil m/2 \rceil$. (For a real number $x$, $\lceil x \rceil$ is the smallest integer that is greater than or equal to $x$.)

For example, suppose girl $1$ wants to stand next to girl $2$, girl $2$ next to girl $3$, girl $3$ next to girl $4$, girl $4$ next to girl $1$, girl $5$ next to girl $6$, and girl $6$ next to girl $5$. Suppose also that girl $1$ and girl $2$ do not want to dance with girl $4$. The group $\{1, 2, 3, 4\}$ satisfies conditions (1) and (2) but not condition (3), because two girls (girls $1$ and $2$) do not want to dance with girl $4$, and $2$ is not less than $\lceil 4/2 \rceil = 2$. Therefore the largest good group is $\{5, 6\}$.

Given every girl's submitted list, write a program that reports the number of girls in the largest good group.

The first line contains the number of test cases $T$.

Each test case starts with a line containing an integer $N$ ($1 \le N \le 10{,}000$), the number of girls. Each of the next $N$ lines describes one girl: line $i$ contains two integers $j$ and $k$, where $j$ is the girl whom girl $i$ wants to stand next to, and $k$ is the girl whom girl $i$ does not want to dance with. If girl $i$ named no disliked girl, then $k$ is $-1$.

For each test case, print a single line containing the number of girls in the largest good group. If there is no good group, print $-1$.