커널 기사단
시간 제한2초메모리 제한512 MB
상대 가문에 속한 기사 한 명을 각자 지목한 2n명의 기사 중에서 사전 순으로 가장 작은 커널을 찾습니다.
문제
마상 창시합은 두 사람이 말을 타고 빠르게 달리면서 나무 창으로 상대를 찌르는 중세의 경기다. 서로 경쟁하는 두 가문에서 기사가 명씩, 모두 명이 대회에 참가했다. 도착한 기사는 저마다 상대 가문의 기사 한 명에게 결투를 신청했다.
기사의 부분집합 가 다음 두 조건을 모두 만족하면 를 커널이라고 한다.
- 에 속한 기사는 에 속한 다른 기사에게 결투를 신청받지 않았다.
- 에 속하지 않은 기사는 모두 에 속한 어떤 기사에게 결투를 신청받았다.
신청된 결투가 모두 주어질 때 커널을 하나 찾아라. 커널은 항상 존재한다.
입력
첫째 줄에 각 가문의 기사 수 이 주어진다 (). 첫 번째 가문의 기사는 번부터 번까지, 두 번째 가문의 기사는 번부터 번까지 번호가 붙어 있다.
둘째 줄에 정수 이 주어진다. 는 번 기사가 결투를 신청한 기사의 번호다 ().
셋째 줄에 정수 이 주어진다. 는 번 기사가 결투를 신청한 기사의 번호다 ().
출력
커널에 속한 기사의 번호를 오름차순으로 정렬해 한 줄에 공백으로 구분해 출력한다.
커널이 여러 개면 그중 사전순으로 가장 작은 것을 출력한다. 즉, 각 커널을 오름차순 수열로 적었을 때 사전순으로 가장 앞서는 수열을 출력한다.