printРабочее место участника

printЗадачи

2455. Секретные уровни

Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

В новом платформере несколько уровней, и игрок может выбрать любой из этих уровней для начала игры. На каждом уровне есть основной выход, после попадания в который игра заканчивается, а также может быть несколько секретных переходов на другие уровни.
Дизайнер игры неправильно спроектировал переходы, и опытный игрок может ходить по кругу между несколькими уровнями и набирать бесконечное количество очков.
Для исправления этой проблемы было решено убрать несколько переходов, чтобы таких циклических переходов между несколькими уровнями не было. При этом желательно убрать не более половины переходов, созданных дизайнером.
Первая строка ввода содержит два целых числа – количество уровней `n` (`1\ ≤\ n\ ≤\ 10^5`) и количество переходов `m` (`0\ ≤\ m\ ≤\ 2*10^5`). Далее следует `m` строк, каждая строка содержит два целых числа `u` и `v` (`1\ ≤\ u,\ v\ ≤\ n`), означающие, что на уровне `u` есть переход на уровень `v`. Гарантируется, что нет переходов с уровня на тот же уровень или дублирующих переходов.
В первой строке выведите количество удаляемых переходов `r` (`0\ ≤\ r\ ≤\ m/2`), далее выведите `r` строк, содержащих по одному целому числу `s` (`1\ ≤\ s\ ≤\ m`) – номера удаляемых переходов.
Не нужно минимизировать `r`, достаточно обеспечить, чтобы `r\ ≤\ m/2`. Если существует несколько вариантов решения, выведите любой из этих вариантов.

Пример ввода 1

2 2
1 2
2 1

Пример вывода 1

1
2

Пример ввода 2

3 3
1 2
2 3
3 1

Пример вывода 2

1
1

Пример ввода 3

4 5
1 2
1 3
2 4
3 2
3 4

Пример вывода 3

0

Пример ввода 4

4 5
1 2
2 3
2 4
3 1
4 1

Пример вывода 4

2
4
5

Пример ввода 5

4 3
1 2
2 3
3 4

Пример вывода 5

1
2
loading