테스트

사라 코너가 아들을 만나려면 클리닉의 주치의인 실버만 박사에게 자신이 제정신이고 판단력이 있다는 것을 증명해야 한다. 박사는 테스트의 하나로 다음 문제를 냈다.

실버만 박사: 내 팔을 부러뜨렸잖아!

사라 코너: 사람 몸에는 뼈가 215개 있어. 방금 그건 그중 하나였을 뿐이야.

《터미네이터 2: 심판의 날》

실버만 박사가 탁자 위에 카드 $n$장을 올려놓는다. 각 카드에는 1부터 $n+1$까지의 자연수가 두 개씩 적혀 있다. 한 카드 안에서 같은 수가 두 번 적힌 경우는 없다. 두 카드가 같은 수의 쌍을 가지는 경우도 없다.

사라는 카드 몇 장을 골라 그 위에 적힌 수를 바꿀 수 있다. 수를 바꾼 뒤에도 모든 카드에 공통으로 적힌 수가 하나 있어야 한다. 위의 조건도 계속 지켜져야 한다. 즉, 카드는 모두 서로 달라야 하고 각 카드의 두 수는 달라야 한다.

사라의 과제는 바꾸는 카드를 가능한 한 적게 하여 이를 해내는 것이다. 그녀를 도와 달라.

첫 줄에 카드의 수 $n$ ($1 \le n \le 100{\,}000$)이 주어진다. 다음 $n$개의 줄에는 카드에 적힌 1부터 $n+1$까지의 서로 다른 두 수가 한 줄에 하나씩 주어진다.

두 카드가 같은 수의 쌍을 가지는 경우는 없고, 두 카드가 수의 순서만 다른 경우도 없다고 보장된다.

사라 코너가 테스트를 통과하려면 바꿔야 하는 카드의 최소 개수 $x$를 한 줄에 출력한다.