만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

열차 운행 취소

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

요약
두 정렬된 기차 번호 목록에서 양쪽에 모두 있는 번호의 개수를 구합니다. 같은 번호의 기차끼리만 충돌하므로 이 개수가 취소할 최소 기차 수입니다.
난이도

쉬움10점 중 2점

유형
배열, 투 포인터
정답자
아직 제출이 없습니다

문제

길동이의 도시에는 아래쪽 끝에서 위쪽 끝으로 이동하는 열차 100100대와 왼쪽 끝에서 오른쪽 끝으로 이동하는 열차 100100대가 있다. 각 방향에서 출발하는 열차에는 11번부터 100100번까지 번호가 붙어 있고, 모든 열차의 속력은 같다. 아래 그림을 보자.

열차 시스템은 2차원 평면의 좌표로 나타낼 수 있다. 아래쪽 끝에서 출발하는 ii번 열차는 처음에 (i,0)(i,0)에 있고, TT분 후에는 (i,T)(i,T)에 있다. 왼쪽 끝에서 출발하는 ii번 열차는 처음에 (0,i)(0,i)에 있고, TT분 후에는 (T,i)(T,i)에 있다. 모든 열차는 101101분 후에 목적지에 도착한다.

길동이는 같은 시각에 출발하도록 편성된 일부 열차가 매우 위험하다는 것을 알아냈다. 이 시각에 아래쪽 끝에서는 nn대, 왼쪽 끝에서는 mm대의 열차가 출발할 예정이다. 어떤 xx와 yy에 대해 두 열차가 같은 시각에 모두 (x,y)(x,y)에 있으면 두 열차는 충돌한다. 모든 충돌을 막기 위해 운행을 취소해야 하는 열차의 최소 대수를 구하라.

입력

첫 줄에 테스트 케이스의 개수 tt(1≤t≤1001\le t\le 100)가 주어진다.

각 테스트 케이스는 세 줄로 이루어진다. 첫 줄에는 아래쪽 끝과 왼쪽 끝에서 출발하는 열차의 대수 nn과 mm(1≤n,m≤1001\le n,m\le 100)이 주어진다. 둘째 줄에는 아래쪽 끝에서 출발하는 열차 번호 nn개가 주어지고, 셋째 줄에는 왼쪽 끝에서 출발하는 열차 번호 mm개가 주어진다. 각 번호는 11 이상 100100 이하이며, 증가하는 순서로 주어진다.

출력

각 테스트 케이스마다 모든 충돌을 막기 위해 운행을 취소해야 하는 열차 대수의 최솟값을 한 줄에 출력한다.

힌트

첫 번째 경우에는 현재 편성대로 운행해도 충돌이 일어나지 않으므로 답은 0이다.

두 번째 경우에는 T=4T=4일 때 충돌이 일어난다(아래 그림 참고). 이 중 열차 한 대를 취소하면 남은 열차끼리는 충돌하지 않으므로 답은 1이다.

예제1

  1. 예제 1

    입력
    3
    1 2
    1
    3 4
    3 2
    1 3 4
    2 4
    9 14
    2 7 16 28 33 57 59 86 99
    3 9 14 19 25 26 28 35 41 59 85 87 99 100
    
    예상 출력
    0
    1
    3