Background

Translated from Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection) D2T1. $\texttt{1s,512M}$.

Problem Description

Given a positive integer \( N \). A partition of the set \( \{1, 2, \ldots, N\} \) is defined as a collection of non-empty sets such that each integer from \( 1 \) to \( N \) appears in exactly one set. For example, \(\{\{1,3\},\{2,4\},\{5\}\}\) is a partition of the set \( \{1, 2, 3, 4, 5\} \).

A partition can be represented by a sequence \( x_1, x_2, \ldots, x_N \), where \( 1 \leq x_i \leq N \). If and only if \( x_i = x_j \), then \( i \) and \( j \) are in the same set. The partition mentioned above \(\{\{1,3\},\{2,4\},\{5\}\}\) can be represented by the array \([1, 2, 1, 2, 3]\) or \([5, 1, 5, 1, 4]\).

Patricija has two partitions: the first partition is represented by the sequence \( a_1, a_2, \ldots, a_N \), and the second partition is represented by the sequence \( b_1, b_2, \ldots, b_N \). Patricija wants to know the answer to the following question: If she uses the sets from these two partitions to construct a partition of the set \( \{1, 2, \ldots, N\} \), what is the minimum number of sets required.

Given a parameter \( k \in \{0, 1, 2\} \):

• When \( k = 0 \), you need to answer the original question.
• When \( k = 1 \), you are allowed to change at most one of the \( 2N \) numbers (\( a_1, \cdots, a_N, b_1, \cdots, b_N \)) to minimize the minimum number of sets required for the partition.
• When \( k = 2 \), you are allowed to change at most one of the \( 2N \) numbers (\( a_1, \cdots, a_N, b_1, \cdots, b_N \)) to maximize the minimum number of sets required for the partition.

Note that you must ensure \( \forall 1 \le i \le N \), \( 1 \le a_i, b_i \le N \) after your modifications.

Input Format

This problem contains multiple test cases within a single test point.

The first line contains two integers \( T \) and \( k \), representing the number of test cases and the parameter, respectively.

The following describes \( T \) test cases:

For each test case, three lines are input:

• The first line contains a positive integer \( N \), as described in the problem statement.
• The second line contains \( N \) positive integers, representing \( a_1, a_2, \cdots, a_N \).
• The third line contains \( N \) positive integers, representing \( b_1, b_2, \cdots, b_N \).

Output Format

For each test case, output a single integer on a new line, representing the answer to the question.

Sample Input and Output

Input Sample #1

2 0
4 
1 1 2 3
1 2 3 3
7
1 1 1 1 2 3 4
1 2 3 4 4 4 4

Output Sample #1

2
4

Input Sample #2

3 1
4
1 1 2 3
1 2 3 3
4
1 1 1 1
1 2 3 3
7
1 1 1 1 2 3 4
1 2 3 4 4 4 4

Output Sample #2

2
1
2

Input Sample #3

3 2
4 
1 1 2 3
1 2 3 3
4
1 1 1 3
1 2 3 3
7
1 1 1 2 3 4 5
1 2 3 4 4 4 4

Output Sample #3

3
3
4

Notes/Hints

Sample Explanation

Sample 1 Explanation:

For the first set of data, the first partition is \(\{\{1,2\},\{3\},\{4\}\}\) and the second partition is \(\{\{1\},\{2\},\{3,4\}\}\). Selecting \(\{1,2\},\{3,4\}\) is sufficient.

For the second set of data, the first partition is \(\{\{1,2,3,4\},\{5\},\{6\},\{7\}\}\) and the second partition is \(\{\{1\},\{2\},\{3\},\{4,5,6,7\}\}\). Selecting either the first or the second partition is sufficient.

Data Range

For \( 100\% \) of the data, it is guaranteed that:

• \( 1 \le T \le 200,000 \), \( k \in \{0, 1, 2\} \);
• \( 1 \le a_i, b_i \le N \);
• \( 1 \le N, \sum N \le 200,000 \).

见题面 Input 部分

见题面 Output 部分