Read problems statements in Mandarin chinese, Russian and Vietnamese as well.

You are given a binary tree with $N$ vertices numbered $1$ through $N$. The root of the tree is vertex $1$. There are two types of vertices:
non-leaf: has exactly two sons — a left son and a right son
leaf: doesn't have sons, but it has an integer value

Let's denote the number of leaves by $L$. It is guaranteed that the values of all leaves are pairwise distinct numbers between $1$ and $L$ inclusive.

To each leaf, we can assign a string in the following way:
consider the simple path $1=v_{1}, v_{2}, \dots, v_{l}$ from the root to leaf $v_{l}$
the string $S_{v_{l}}$ assigned to leaf $v_{l}$ has length $l-1$; for each valid $i$, $S_{i}$ is 'L' if $v_{i+1}$ is the left son of $v_{i}$ or 'R' if it's the right son of $v_{i}$

It's clear that these strings are all pairwise distinct. Let's call the tree leaf-sorted if the following property holds for every pair of different leaves $a, b$: $S_{a}$ is lexicographically smaller than $S_{b}$ if and only if the value of $a$ is smaller than the value of $b$.

You are allowed to perform the following operation an arbitrary number of times (including zero): choose a non-leaf vertex and swap the edges to its left and right son. That is, the original left son of this vertex becomes the right son and the original right son becomes the left son (along with their whole subtrees).

Find the minimum number of operations needed to make the tree leaf-sorted, or determine that it's impossible.

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
$N$ lines follow. For each $i$ ($1 ≤ i ≤ N$), the $i$-th of these lines contains two space-separated integers $l$ and $r$. If $l = -1$, vertex $i$ is a leaf with value $r$. Otherwise, $l$ and $r$ respectively denote the left and right son of vertex $i$.

------ Output ------
For each test case, print a single line containing one integer — the minimum required number of operations or $-1$ if it's impossible to make the tree leaf-sorted.

------ Constraints ------
$1 ≤ T ≤ 1,000$
$2 ≤ N ≤ 10^{5}$
$1 ≤ r ≤ L$ for each leaf ($l = -1$)
$1 ≤ l, r ≤ N$ for each non-leaf
the values of all leaves are pairwise distinct
the graph described on the input is a binary tree rooted at vertex $1$
the sum of $N$ for all test cases does not exceed $2 \cdot 10^{5}$

------ Subtasks ------

Subtask #1 (30 points):
$1 ≤ T ≤ 100$
$2 ≤ N ≤ 30$

Subtask #2 (20 points):
$1 ≤ T ≤ 100$
$2 ≤ N ≤ 1,000$
the sum of $N$ for all test cases does not exceed $2,000$

Subtask #3 (50 points): original constraints

----- Sample Input 1 ------
2
5
3 5
-1 2
2 4
-1 3
-1 1
7
2 3
4 5
6 7
-1 1
-1 4
-1 3
-1 2
----- Sample Output 1 ------
1
-1
----- explanation 1 ------
Example case 1: The leaves of this tree are vertices $2, 4, 5$, the strings assigned to them are "LL", "LR", "R" and their values are $2, 3, 1$. The strings are in increasing order and the corresponding values are not, so the tree isn't leaf-sorted. However, if we swap the left and right son of the root (vertex $1$), the strings assigned to the vertices become "RL, "RR", "L", so the tree becomes leaf-sorted.

见题面

见题面