e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

Strong Connected Components

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

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

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

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

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

Вхідні дані

У першому рядку задано число будинків n (1n3000). У другому рядку записано кількість доріг m (1m100000). Далі йде опис доріг у форматі aibi, який означає, що по i-ій дорозі дозволяється рух автотранспорту від будинку ai до будинку bi (1ai, bin).

Вихідні дані

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

prb1937.gif

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
5
7
1 2
2 3
3 1
2 1
2 3
3 4
2 5
Вихідні дані #1
2
4 5
Автор Віталій Гольдштейн
Джерело 2011 Зимова Школа, Харків, День 9