Phoenix and Socks

Description:

Input:

The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The first line of each test case contains three integers $$$n$$$, $$$l$$$, and $$$r$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$n$$$ is even; $$$0 \le l, r \le n$$$; $$$l+r=n$$$) — the total number of socks, and the number of left and right socks, respectively.

The next line contains $$$n$$$ integers $$$c_i$$$ ($$$1 \le c_i \le n$$$) — the colors of the socks. The first $$$l$$$ socks are left socks, while the next $$$r$$$ socks are right socks.

It is guaranteed that the sum of $$$n$$$ across all the test cases will not exceed $$$2 \cdot 10^5$$$.

Output:

For each test case, print one integer — the minimum cost for Phoenix to make $$$n/2$$$ matching pairs. Each sock must be included in exactly one matching pair.

Sample Input:

4
6 3 3
1 2 3 2 2 2
6 2 4
1 1 2 2 2 2
6 5 1
6 5 4 3 2 1
4 0 4
4 4 4 3

Sample Output:

2
3
5
3

Note:

In the first test case, Phoenix can pay $$$2$$$ dollars to:

• recolor sock $$$1$$$ to color $$$2$$$
• recolor sock $$$3$$$ to color $$$2$$$

There are now $$$3$$$ matching pairs. For example, pairs $$$(1, 4)$$$, $$$(2, 5)$$$, and $$$(3, 6)$$$ are matching.

In the second test case, Phoenix can pay $$$3$$$ dollars to:

• turn sock $$$6$$$ from a right sock to a left sock
• recolor sock $$$3$$$ to color $$$1$$$
• recolor sock $$$4$$$ to color $$$1$$$

There are now $$$3$$$ matching pairs. For example, pairs $$$(1, 3)$$$, $$$(2, 4)$$$, and $$$(5, 6)$$$ are matching.