Легендарный фермер Джон готовит большую вечеринку. В гости были приглашены животные со всего мира. Сейчас гости проголодались, так что Джон попросил свою корову Бесси достать чего-нибудь перекусить.
Есть \(n\) разных видов закусок, пронумерованных числами \(1, 2, \ldots, n\). У Бесси есть \(n\) закусок, по одной закуске каждого вида. У каждого гостя есть ровно два любимых вида закусок. Процесс перекуса будет происходить следующим образом:
- Сначала Бесси упорядочит всех гостей в каком-то порядке.
- Затем, в этом порядке гости будут по одному подходить к закускам.
- Каждый гость будет в свой ход съедать все оставшиеся закуски любимых типов. В случае, если не осталось ни одной закуски любимых типов, то гость уйдёт очень грустным.
Помогите Бесси минимизировать число грустных гостей, упорядочив гостей правильным образом.
Выходные данные
Выведите одно целое число — минимальное возможное количество грустных гостей.
Примечание
В первом примере Бесси может упорядочить гостей следующим образом: \(3, 1, 2, 4\). Гость \(3\) пойдёт первым и съест закуски \(1\) и \(4\). Затем идёт гость \(1\) и съедает закуску \(2\), так как закуска \(1\) уже съедена. Затем приходит гость \(2\) и съедает только закуску \(3\). Так как все закуски уже съедены, то гость \(4\) будет грустным.
Во втором примере можно упорядочить гостей как \(2, 1, 3, 5, 4\). Тогда все гости будут удовлетворены.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4
1 2
4 3
1 4
3 4
|
1
|
|
2
|
6 5
2 3
2 1
3 4
6 5
4 5
|
0
|