만드는 중입니다

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

수강변경

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

요약
각 학생은 A_i 과목을 가지고 있고 B_i 과목을 원한다. 두 학생이 서로 과목을 교환할 수 있고 연쇄 교환도 가능할 때, 원하는 과목을 받지 못하는 학생 수의 최솟값을 구한다.
난이도

보통10점 중 6점

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

문제

20XX년, 전국에서 유일하게 마일리지 수강신청 제도를 쓰는 연세대는 수강변경에서도 새로운 시스템을 도입하려고 한다.

20XX년부터 수강변경 기간에는 "수업 교환"이 허용된다.

수업 교환은 두 사람이 서로 다른 수업을 맞바꾸는 것이며, 두 사람 모두 동의해야만 성사된다.

삼자 교환은 할 수 없지만, 두 사람이 수업을 교환한 뒤 그중 한 사람이 그 수업을 또 다른 사람과 교환하는 것은 허용된다.

제도가 처음 도입되었을 때는 말이 많았지만, 서로의 전공 수업을 듣고 싶은 학생들이 수업을 교환하거나 마일리지가 많이 남는 졸업 예정자들이 후배들에게 수업을 넘겨주는 등 좋은 사례가 늘고 있다.

여느 때처럼 수강변경이 시작되었다. 학생마다 듣고 싶은 수업이 11개씩 주어지고, 교환하고 싶은 수업이 11개씩 주어질 때, 수업 교환이 끝난 뒤 본인이 원하는 수업을 듣지 못하는 학생 수의 최솟값을 구해 보자.

입력

첫 줄에 학생 수 NN이 주어진다. (1≤N≤1 000 0001 \leq N \leq 1\ 000\ 000)

둘째 줄에 정수 A1,A2,⋯ ,ANA_1, A_2, \cdots, A_N이 주어진다. AiA_i는 ii번 학생이 현재 신청한 수업이자 교환하고 싶은 수업의 번호다. (1≤Ai≤1 000 0001 \leq A_i \leq 1\ 000\ 000)

셋째 줄에 정수 B1,B2,⋯ ,BNB_1, B_2, \cdots, B_N이 주어진다. BiB_i는 ii번 학생이 교환을 통해 듣고 싶은 수업의 번호다. (1≤Bi≤1 000 0001 \leq B_i \leq 1\ 000\ 000)

모든 입력은 공백으로 구분되어 주어진다.

출력

모든 학생이 최적의 방법으로 수업 교환을 마쳤을 때, 원하는 수업을 듣지 못하는 학생 수를 출력한다.

예제2

  1. 예제 1

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

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