B - Incomplete Shuffle Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 800 点

問題文

正整数 N と長さ N の整数列 A=(A_1,A_2,\ldots,A_N),B=(B_1,B_2,\ldots,B_N) が与えられます。

あなたは A に対して N-1 回の操作を行います。i 回目 (1\le i\le N-1) の操作は以下の通りです：

  • i < j \le N を満たす整数 j を選び、A_i と A_j の値を入れ替える。

N-1 回の操作を終えた後に A_k=B_k を満たす k (1\le k\le N) の個数の最大値を求めてください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1\le T\le 10^5
  • 2\le N\le 3\times 10^5
  • 1\le A_i,B_i\le N
  • 全てのテストケースにおける N の総和は 3\times 10^5 以下
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

各テストケースは以下の形式で与えられる。

N
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N

出力

各テストケースに対する答えを順に改行区切りで出力せよ。

入力例 1

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

出力例 1

2
2
5

1 番目のテストケースについて考えます。

以下のように操作することで、N-1 回の操作を終えた後に A_k=B_k を満たす k の個数を 2 個にできます。

  • i=1 のとき：j=2 を選ぶ。A=(1,1,2) となる。
  • i=2 のとき：j=3 を選ぶ。A=(1,2,1) となる。

N-1 回の操作を終えた後に A_k=B_k を満たす k の個数を 2 個より多くすることはできないので、1 行目には 2 を出力してください。

Score : 800 points

Problem Statement

You are given a positive integer N and integer sequences of length N: A=(A_1,A_2,\ldots,A_N) and B=(B_1,B_2,\ldots,B_N).

You perform N-1 operations on A. The i-th operation (1\le i\le N-1) is as follows:

  • Choose an integer j satisfying i < j \le N, and swap the values of A_i and A_j.

Find the maximum possible number of indices k (1\le k\le N) satisfying A_k=B_k after N-1 operations.

You are given T test cases; solve each of them.

Constraints

  • 1\le T\le 10^5
  • 2\le N\le 3\times 10^5
  • 1\le A_i,B_i\le N
  • The sum of N over all test cases is at most 3\times 10^5.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format:

N
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N

Output

Output the answers for the test cases in order, separated by newlines.

Sample Input 1

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

Sample Output 1

2
2
5

Consider the first test case.

By performing the operations as follows, the number of indices k satisfying A_k=B_k after N-1 operations can be made 2.

  • When i=1: choose j=2. A=(1,1,2).
  • When i=2: choose j=3. A=(1,2,1).

The number of indices k satisfying A_k=B_k after N-1 operations cannot be made greater than 2, so output 2 on the first line.