아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

커널 기사단

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

요약
상대 가문에 속한 기사 한 명을 각자 지목한 2n명의 기사 중에서 사전 순으로 가장 작은 커널을 찾습니다.
난이도

어려움10점 중 8점

유형
그래프, 그리디
정답자
아직 제출이 없습니다

문제

마상 창시합은 두 사람이 말을 타고 빠르게 달리면서 나무 창으로 상대를 찌르는 중세의 경기다. 서로 경쟁하는 두 가문에서 기사가 nn명씩, 모두 2n2n명이 대회에 참가했다. 도착한 기사는 저마다 상대 가문의 기사 한 명에게 결투를 신청했다.

기사의 부분집합 SS가 다음 두 조건을 모두 만족하면 SS를 커널이라고 한다.

  • SS에 속한 기사는 SS에 속한 다른 기사에게 결투를 신청받지 않았다.
  • SS에 속하지 않은 기사는 모두 SS에 속한 어떤 기사에게 결투를 신청받았다.

신청된 결투가 모두 주어질 때 커널을 하나 찾아라. 커널은 항상 존재한다.

입력

첫째 줄에 각 가문의 기사 수 nn이 주어진다 (1≤n≤100 0001 \le n \le 100\,000). 첫 번째 가문의 기사는 11번부터 nn번까지, 두 번째 가문의 기사는 n+1n+1번부터 2n2n번까지 번호가 붙어 있다.

둘째 줄에 정수 f1,f2,…,fnf_1, f_2, \dots, f_n이 주어진다. fkf_k는 kk번 기사가 결투를 신청한 기사의 번호다 (n+1≤fk≤2nn+1 \le f_k \le 2n).

셋째 줄에 정수 s1,s2,…,sns_1, s_2, \dots, s_n이 주어진다. sks_k는 n+kn+k번 기사가 결투를 신청한 기사의 번호다 (1≤sk≤n1 \le s_k \le n).

출력

커널에 속한 기사의 번호를 오름차순으로 정렬해 한 줄에 공백으로 구분해 출력한다.

커널이 여러 개면 그중 사전순으로 가장 작은 것을 출력한다. 즉, 각 커널을 오름차순 수열로 적었을 때 사전순으로 가장 앞서는 수열을 출력한다.

예제4

  1. 예제 1

    입력
    4
    5 6 7 7
    1 3 2 3
    
    예상 출력
    1 2 4 8
    
  2. 예제 2

    입력
    1
    2
    1
    
    예상 출력
    1
    
  3. 예제 3

    입력
    2
    3 3
    1 1
    
    예상 출력
    2 4
    
  4. 예제 4

    입력
    6
    7 8 9 10 11 12
    1 2 3 4 5 6
    
    예상 출력
    1 2 3 4 5 6