16474번 - 이상한 전깃줄

엘리트 도로설계사 현정이는 도로 위 전봇대 사이에 연결된 전깃줄을 관리하는 일을 한다. 도로 양 옆에는 각 고유번호를 갖고 있는 전봇대가 여러 개 있다. 마을에 최대한 많은 양의 전력을 보급하기 위해선 전깃줄이 서로 교차하지 않도록 하면서 불필요한 전깃줄을 최소한으로 제거해야 한다.

어느 날 현정이는 전력난으로 고통받는 동네에 파견이 되었다. 한 동네의 전력난을 해결해 줄 심상으로 자신감 넘치게 문제의 동네로 간 현정이는 경악을 금치 않을 수 없었다. 그 동네는 현정이가 그동안 봐왔던 그 어떤 동네보다도 이상하고 복잡한 동네였다. 일반적인 동네는 전봇대의 번호가 오름차순으로 정렬이 되어 있는 반면, 현정이가 파견된 동네는 전봇대의 번호가 뒤죽박죽이었다. 더구나 위험하게 한 전봇대에 전깃줄이 여러 개 연결되기도 했다. 이런 경우 사고 방지를 위해서, 한 전봇대에 연결된 전깃줄의 개수를 한 개 이하로 줄여야 한다.

현정이는 엘리트 도로설계사라는 프라이드를 지키기 위해 제거할 전깃줄의 수를 최소화하려고 한다. 이런 현정이를 위해 최소한 몇 개의 전깃줄을 제거해야 하는지 알려주자.

첫 번째 줄에 도로 양변의 전봇대의 개수 정수 N과 M이 주어진다.

두 번째 줄에 도로 왼편의 전봇대의 번호가 1 이상 N 이하의 서로 다른 정수로 주어진다.

세 번째 줄에 도로 오른편의 전봇대의 번호가 1 이상 M 이하의 서로 다른 정수로 주어진다.

네 번째 줄에는 전깃줄의 개수 K개 주어진다.

다섯 번째 줄부터 한 줄에 하나씩 전깃줄이 도로 왼편과 연결되는 전봇대의 번호와, 도로 오른편과 연결되는 전봇대의 번호가 차례로 주어진다. 이때 중복되어 설치되어 있는 전깃줄은 없다.

N, M은 2,000 이하의 자연수이고, K는 200,000 이하의 자연수다. 

제거해야 하는 전깃줄 개수의 최솟값을 출력한다.