Empty Sofa - Repovive Starter Round 9 | Repovive

25G. Empty Sofa

3500 pts2s256 MB

There are $n$ guests and $n+1$ sofas, numbered from $1$ to $n$ and from $1$ to $n+1$ , respectively. Guest $i$ has size $a_i$ , and sofa $j$ has capacity $b_j$ . Each sofa can hold at most one guest, and guest $i$ can sit on sofa $j$ only if $a_i \le b_j$ .

Initially, guest $i$ is sitting on sofa $p_i$ and wants to end up on sofa $q_i$ . Both arrangements are valid: the guests occupy distinct sofas, and every guest fits on their sofa.

In one move, choose a guest and move them to the empty sofa, provided that they fit on it. Their previous sofa becomes empty.

Find the minimum number of moves needed to reach the desired arrangement. If it is impossible, output $-1$ .

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le a_i, b_j \le 10^9$
$1 \le p_i, q_i \le n+1$
The values $p_1,\ldots,p_n$ are pairwise distinct.
The values $q_1,\ldots,q_n$ are pairwise distinct.
$a_i \le b_{p_i}$ and $a_i \le b_{q_i}$ for every guest $i$ .
The sum of $n$ over all test cases is at most $2 \times 10^5$ .

Input

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \\ b_1 \quad b_2 \quad \cdots \quad b_{n+1} \\ p_1 \quad p_2 \quad \cdots \quad p_n \\ q_1 \quad q_2 \quad \cdots \quad q_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

Samples

Input

Case 1

Case 2

Explanation

Case 1

The initial arrangement already matches the desired arrangement, so no moves are needed.

Case 2

The empty sofa has capacity 1, but both guests have size 2. No move is possible, and the guests are not in their desired positions.

Output

Case 1

Case 2

-1

Input

Case 1

Case 2

Case 3

Explanation

Case 1

Move guest 1 from sofa 1 to sofa 2, then move guest 2 from sofa 3 to sofa 1. Both guests must change sofas, so two moves are necessary.

Case 2

Move guest 1 to sofa 1, guest 2 to sofa 2, guest 3 to sofa 3, guest 2 to sofa 4, and guest 1 back to sofa 2. Initially, only guest 1 can move to the empty sofa, and they must eventually return. Guests 2 and 3 need at least three moves to exchange their sofas, so at least five moves are needed.

Case 3

Move guest 1 to sofa 1, guest 3 to sofa 2, guest 4 to sofa 4, guest 3 to sofa 5, guest 2 to sofa 2, and guest 1 to sofa 3. Guests 1 and 2 exchange their sofas, as do guests 3 and 4. In each pair, the first guest to move must move again because their destination is occupied. Therefore, at least six moves are needed.

Output

Case 1

Case 2

Case 3

Initially, guest $i$ is sitting on sofa $p_i$ and wants to end up on sofa $q_i$ . Both arrangements are valid: the guests occupy distinct sofas, and every guest fits on their sofa.

In one move, choose a guest and move them to the empty sofa, provided that they fit on it. Their previous sofa becomes empty.

Find the minimum number of moves needed to reach the desired arrangement. If it is impossible, output $-1$ .

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le a_i, b_j \le 10^9$
$1 \le p_i, q_i \le n+1$
The values $p_1,\ldots,p_n$ are pairwise distinct.
The values $q_1,\ldots,q_n$ are pairwise distinct.
$a_i \le b_{p_i}$ and $a_i \le b_{q_i}$ for every guest $i$ .
The sum of $n$ over all test cases is at most $2 \times 10^5$ .

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \\ b_1 \quad b_2 \quad \cdots \quad b_{n+1} \\ p_1 \quad p_2 \quad \cdots \quad p_n \\ q_1 \quad q_2 \quad \cdots \quad q_n \end{array} \right\} \times t

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

25G. Empty Sofa

Constraints

Input

Output

Samples

25G. Empty Sofa

Constraints

Input

Output

Samples