Тестирование

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

요약

1부터 n+1까지의 서로 다른 두 수로 이루어진 n개의 카드 쌍이 주어질 때, 공통으로 등장하는 수가 생기도록 최소 개수의 카드를 바꾸는 문제입니다.

난이도: 보통10점 중 7점
유형: 그래프, 그리디, 수학
정답자: 아직 제출이 없습니다

문제

--- Доктор Сильберман: Ты мне руку сломала!

--- Cара Коннор: В человеческом организме 215 костей. Это была только одна.

<<Терминатор 2: Судный день>>

Чтобы добиться возможности видеть своего сына, Саре необходимо доказать доктору Сильберману, главному врачу клиники, свою адекватность и дееспособность. В качестве одного из тестов доктор предложил Саре следующую задачу.

Доктор выкладывает на стол $n$ карточек, на каждой из которых написано по два натуральных числа, каждое из которых находится в интервале от одного до $n + 1$ . В этом наборе ни на одной карточке не написаны одинаковые числа. Кроме этого, не существует двух карточек с одинаковой парой чисел.

Сара может выбрать несколько карточек и изменить написанные на них числа. После изменений, внесенных Сарой, должно существовать число, написанное на всех карточках. Кроме этого должны быть выполнены условия, описанные выше --- уникальность карточек и несовпадение чисел на любой из них.

Задача Сары состоит в том, чтобы сделать это, изменив как можно меньше карточек. Помогите ей сделать это.

입력

В первой строке дано одно целое число $n$ ( $1 \le n \le 100{\\,}000$ ) --- количество карточек, выложенных на стол доктором. Следующие $n$ строк содержат по два различных числа от одного до $n + 1$ --- числа, написанные на карточках.

Гарантируется, что не существует двух карточек с одинаковой парой чисел, или двух карточек, числа на которых отличаются только порядком их записи.

출력

В единственной строке выведите число $x$ --- минимальное количество карточек, которые требуется изменить Саре Коннор для прохождения теста.

예제1

예제 1
입력
```
4
1 2
2 3
3 4
4 5
```
예상 출력
```
2
```