Коровы Фермера Джона съедают на завтрах по ящику зерна!
На ферму поступили \(M\) различных типов зерна \((2\le M\le 10^5)\).
К несчастью, есть только один ящик зерна каждого типа. Каждая из
\(N\) коров \((1\le N\le 10^5)\) имеет первый и второй любимые типы зерна.
Когда корове приходит время выбирать, она выполняет следующий процесс:
- Если ящик с её любимым типом еще есть, она берёт его и отходит
- Иначе если ящик с её вторым любимым типом зерна ещё есть, она берёт его и отходит
- Иначе она не берёт ничего
Определите минимальное количество коров, которые останутся голодными
при оптимальном порядке выбора. Выведите любую перестановку из \(N\) коров (порядок),
при которой достигается этот минимум.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит два разделённых пробелом целых числа
\(N\) и
\(M.\)
Для каждого \(1\le i\le N,\) \(i\)-ая строка содержит два разделённых пробелом целых числа
\(f_i\) и \(s_i\) (\(1\le f_i,s_i\le M\) и \(f_i\neq s_i\)) которые обозначают номера типов
первого и второго любимого зерна \(i\)-ой коровы.
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите минимальное количество коров, которые уйдут голодными, за которой следует
любая перестановка \(1\ldots N\), при которой достигается этот минимум.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8 10
2 1
3 4
2 3
6 5
7 8
6 7
7 5
5 8
|
1
1
3
2
8
4
6
5
7
|