K. Colored Dominoes
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Manuel loves puzzles and is trying to solve one involving a row of $$$n$$$ dominoes, each placed vertically. Initially, the positions are numbered from $$$1$$$ to $$$n$$$ from left to right.

The domino initially at position $$$i$$$ has number $$$a_i$$$ on its upper half and number $$$b_i$$$ on its lower half. Across all $$$2n$$$ halves, each integer from $$$1$$$ to $$$2n$$$ appears exactly once.

Each domino also has a color, represented by an integer. The domino initially at position $$$i$$$ has color $$$c_i$$$. Manuel may perform either of the following operations any number of times:

  • Choose a domino and swap the numbers on its upper and lower halves.
  • Choose two dominoes of the same color and swap their positions in the row.

His goal is to arrange the dominoes so that, when read from left to right, both the upper numbers and the lower numbers form strictly increasing sequences.

Before performing any operations, Manuel may repaint some dominoes. Each repainted domino may be assigned any integer color from $$$1$$$ to $$$n$$$.

Determine the minimum number of dominoes he must repaint to solve the puzzle. If it is impossible regardless of which dominoes he repaints and which colors he chooses, print $$$-1$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^{4}$$$), the number of test cases.

Each test case consists of four lines.

The first contains an integer $$$n$$$ ($$$1 \le n \le 10^{6}$$$), the number of dominoes.

The second contains $$$n$$$ integers $$$a_1,\ldots,a_n$$$ ($$$1 \le a_i \le 2n$$$), the initial upper numbers.

The third contains $$$n$$$ integers $$$b_1,\ldots,b_n$$$ ($$$1 \le b_i \le 2n$$$), the initial lower numbers.

Together, $$$a$$$ and $$$b$$$ form a permutation of the integers from $$$1$$$ to $$$2n$$$.

The fourth contains $$$n$$$ integers $$$c_1,\ldots,c_n$$$ ($$$1 \le c_i \le n$$$), the initial colors.

The sum of $$$n$$$ over all test cases does not exceed $$$10^{6}$$$.

Output

For each test case, print the minimum number of dominoes Manuel must repaint on a separate line, or $$$-1$$$ if the goal is impossible.

Example
Input
2
5
7 3 9 5 6
2 8 4 10 1
1 2 1 3 1
6
10 2 12 4 3 8
7 5 11 9 1 6
2 1 3 2 3 1
Output
2
-1
Note

Explanation for example 1

In the first test case, Manuel can repaint dominoes $$$2$$$ and $$$4$$$ with color $$$1$$$. All dominoes then have the same color, so any two may be swapped. After swapping and flipping some dominoes, he can obtain $$$1,2,3,4,5$$$ on the upper halves and $$$6,7,8,9,10$$$ on the lower halves. The minimum cost is $$$2$$$.

In the second test case, it is impossible to make both rows increasing, even if all dominoes could be freely rearranged. The answer is therefore $$$-1$$$.