교차 짝맞추기

시간 제한1초메모리 제한128 MB

요약

두 행에 놓인 양의 정수 사이에서 같은 값을 잇는 선분을 그리되, 각 선분이 정확히 하나의 다른 선분과 교차하고 어떤 수도 두 번 쓰이지 않도록 최대 개수를 구한다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 배열, 투 포인터, 조합론
정답자: 아직 제출이 없습니다

문제

두 줄에 걸쳐 양의 정수들이 나열되어 있다. 값이 같은 두 수가 서로 다른 줄에(하나는 첫째 줄, 다른 하나는 둘째 줄에) 있을 때, 그 두 수를 하나의 선분으로 이을 수 있다. 이 선분의 값이 $r$ 이면 이를 $r$ -선분이라고 부른다. 아래 그림은 3-선분과 2-선분의 예이다.

주어진 입력에 대해, 다음 조건을 모두 만족하도록 선분을 그릴 때 그릴 수 있는 선분의 최대 개수를 구하려고 한다.

값이 $a$ 인 선분은 값이 $b$ 인 선분과 정확히 하나만 교차해야 하며, 이때 $a \neq b$ 이다.
한 수에서 두 개 이상의 선분이 나올 수 없다(각 수는 최대 하나의 선분에만 사용된다). 예를 들어 아래와 같은 짝맞추기는 허용되지 않는다.

선분의 최대 개수를 구하는 프로그램을 작성하라. 이 값은 항상 짝수임에 유의한다.

입력

첫째 줄에 테스트 케이스의 수 $M$ 이 주어진다 ( $1 \le M \le 10$ ). 각 테스트 케이스는 세 줄로 이루어진다. 첫째 줄에는 첫째 줄과 둘째 줄에 있는 정수의 개수 $N_1$ 과 $N_2$ 가 주어진다. 다음 줄에는 첫째 줄의 정수 $N_1$ 개가, 그 다음 줄에는 둘째 줄의 정수 $N_2$ 개가 주어진다. 모든 수는 $100$ 보다 작은 양의 정수이다.

출력

각 테스트 케이스마다 한 줄에 하나씩, 그릴 수 있는 선분의 최대 개수를 출력한다.

예제4

예제 1

입력

3
6 6
1 3 1 3 1 3
3 1 3 1 3 1
4 4
1 1 3 3 
1 1 3 3 
12 11
1 2 3 3 2 4 1 5 1 3 5 10
3 1 2 3 2 4 12 1 5 5 3

예상 출력

6
0
8

예제 2
입력
```
1
2 2
1 2
2 1
```
예상 출력
```
2
```
예제 3
입력
```
1
3 3
1 2 3
1 2 3
```
예상 출력
```
0
```
예제 4
입력
```
1
3 3
5 6 7
1 2 3
```
예상 출력
```
0
```