승진

헨리크 씨의 회사가 크게 성장하여 많은 신입 직원을 채용하기로 했습니다. 이에 따라 조직을 전면적으로 개편하게 되었고, 기존 직원 중 상당수가 새로 만들어진 관리직으로 승진하게 됩니다. 이런 계획은 신중하게 세워야 하므로, 헨리크 씨는 인사 담당 보좌관에게 도움을 청했습니다.

두 사람은 함께 (직위, 직원) 쌍의 목록을 만들었습니다. 각 쌍은 해당 직원이 해당 직위를 맡을 수 있음을 뜻합니다. 그런 다음 각자 자신만의 승진 계획을 세웠습니다. 사장인 헨리크 씨는 반드시 채워야 한다고 생각하는 직위가 모두 채워지도록 했고, 인사 보좌관은 승진할 자격이 가장 큰 사람들이 모두 승진하도록 했습니다. 안타깝게도 두 계획은 서로 많이 달랐습니다.

그래서 헨리크 씨는 자신의 계획에 있는 중요한 직위를 모두 채우면서 동시에 보좌관의 계획에 있는 직원을 모두 승진시키는 하나의 승진 계획을 원합니다. 승진 계획이란 허용된 쌍만을 사용해 직원을 직위에 배정하는 것으로, 각 직원은 최대 한 개의 직위만 맡고 각 직위는 최대 한 명의 직원만 맡습니다. 두 조건을 모두 만족하는 계획 중에서, 승진 인원이 가능한 한 적은 계획을 찾으려 합니다.

첫째 줄에 테스트 케이스의 수 $Z$ ($Z = 1$)가 주어집니다. 이어서 각 테스트 케이스의 설명이 주어집니다.

각 테스트 케이스의 첫째 줄에는 세 정수 $s$, $p$, $m$ ($1 \le s, p \le 100\,000$, $1 \le m \le 300\,000$)이 주어지며, 각각 채워야 할 직위의 수, 직원의 수, 허용된 승진 쌍의 수를 뜻합니다. 이어지는 $m$개의 줄에는 각각 두 정수 $a$, $b$ ($1 \le a \le s$, $1 \le b \le p$)가 주어지며, 직원 $b$가 직위 $a$를 맡을 수 있음을 뜻합니다. 이 쌍들은 주어진 순서대로 $1$번부터 $m$번까지 번호가 매겨집니다.

그다음 두 개의 승진 계획이 주어집니다. 먼저 사장의 계획, 그다음 보좌관의 계획입니다. 각 계획은 두 줄로 이루어집니다. 첫째 줄에는 정수 $n$ ($1 \le n \le m$)이, 둘째 줄에는 $n$개의 정수 $x$ ($1 \le x \le m$)가 주어지며, 이는 그 계획이 사용하는 쌍들의 (허용된 승진 목록에서의) 번호입니다. 한 계획 안에서 각 직원은 최대 한 개의 직위만 맡고 각 직위는 최대 한 명의 직원만 맡으므로, 각 계획은 그 자체로 올바른 배정입니다.

사장의 계획이 채우는 직위들의 집합을 $P$, 보좌관의 계획이 승진시키는 직원들의 집합을 $E$라고 합시다. 통합 계획이란 허용된 쌍만 사용하고 각 직위와 각 직원을 최대 한 번만 사용하는 올바른 배정으로서, $P$에 속한 모든 직위를 채우고 $E$에 속한 모든 직원을 승진시키는 것입니다.

각 테스트 케이스마다, 가능한 모든 통합 계획 중에서 승진 인원(즉 선택한 쌍의 개수)의 최솟값을 한 줄에 출력하세요. 통합 계획이 존재하지 않으면 대신 $-1$을 출력합니다.

입력으로 주어지는 두 계획은 각각 올바른 배정임이 보장됩니다.

첫 번째 예시에서 사장은 직위 $2$, $1$, $3$이 채워지기를 원하고, 보좌관은 직원 $4$와 $1$이 승진하기를 원합니다. 직원 $2$를 직위 $1$에, 직원 $4$를 직위 $2$에, 직원 $1$을 직위 $3$에 배정하면 필요한 세 직위가 모두 채워지고 필요한 두 직원이 모두 승진하며, 승진 인원은 $3$명으로 가능한 최소입니다.