수강변경
시간 제한4초메모리 제한512 MB
각 학생은 A_i 과목을 가지고 있고 B_i 과목을 원한다. 두 학생이 서로 과목을 교환할 수 있고 연쇄 교환도 가능할 때, 원하는 과목을 받지 못하는 학생 수의 최솟값을 구한다.
문제
20XX년, 전국에서 유일하게 마일리지 수강신청 제도를 쓰는 연세대는 수강변경에서도 새로운 시스템을 도입하려고 한다.
20XX년부터 수강변경 기간에는 "수업 교환"이 허용된다.
수업 교환은 두 사람이 서로 다른 수업을 맞바꾸는 것이며, 두 사람 모두 동의해야만 성사된다.
삼자 교환은 할 수 없지만, 두 사람이 수업을 교환한 뒤 그중 한 사람이 그 수업을 또 다른 사람과 교환하는 것은 허용된다.
제도가 처음 도입되었을 때는 말이 많았지만, 서로의 전공 수업을 듣고 싶은 학생들이 수업을 교환하거나 마일리지가 많이 남는 졸업 예정자들이 후배들에게 수업을 넘겨주는 등 좋은 사례가 늘고 있다.
여느 때처럼 수강변경이 시작되었다. 학생마다 듣고 싶은 수업이 개씩 주어지고, 교환하고 싶은 수업이 개씩 주어질 때, 수업 교환이 끝난 뒤 본인이 원하는 수업을 듣지 못하는 학생 수의 최솟값을 구해 보자.
입력
첫 줄에 학생 수 이 주어진다. ()
둘째 줄에 정수 이 주어진다. 는 번 학생이 현재 신청한 수업이자 교환하고 싶은 수업의 번호다. ()
셋째 줄에 정수 이 주어진다. 는 번 학생이 교환을 통해 듣고 싶은 수업의 번호다. ()
모든 입력은 공백으로 구분되어 주어진다.
출력
모든 학생이 최적의 방법으로 수업 교환을 마쳤을 때, 원하는 수업을 듣지 못하는 학생 수를 출력한다.