eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Протипожежна безпека

Протипожежна безпека

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

У місті Зеленоград n будинків. Деякі з них з'єднані дорогами з одностороннім рухом.

В останній час у Зеленограді почастішали випадки пожеж. У зв'язку з цим жителі вирішили побудувати у місті декілька пожежних станцій. Але виникла проблема — пожежна машина, яка їде на виклик, звичайно, може ігноувати напрямок руху поточної дороги, проте, повертаючись із заідання машина зобов'язана дотримуватись правил дорожнього руху (жителі Зеленограда свято поважають ці правила!).

Ясно, що де б не опинилась пожежна машина, у неї повинна бути можливість повернутись на ту пожежну станцію, з якої виїхала. Але будівництво станцій коштує великих грошей, тому на раді міста було вирішено побудувати мінімальну кількість станцій таким чином, щоб ці умови виконувались. Крім того, для економії було вирішено будувати станції у вигляді прибудов до вже існуючих будинків.

Ваша задача — написати програму, яка розраховує оптимальне положення станцій.

Вхідні дані

У першому рядку задано число будинків n~(1 \le n \le 3000). У другому рядку записано кількість доріг m~(1 \le m \le 10^5). Далі йде опис доріг у форматі a_i~b_i, який означає, що по i-ій дорозі дозволяється рух автотранспорту від будинку a_i до будинку b_i~(1 \le a_i, b_i \le n).

Вихідні дані

У першому рядку виведіть мінімальну кількість пожежних станцій k, які необхідно побудувати. У другому рядку виведіть k чисел у довільному порядку — будинки, до яких необхідно прибудувати станції. Якщо оптимальних розв'язків декілька, виведіть довільний.

Приклад

Вхідні дані #1
5
7
1 2
2 3
3 1
2 1
2 3
3 4
2 5
Вихідні дані #1
2
4 5
Автор Віталій Гольдштейн
Джерело 2011 Зимова Школа, Харків, День 9