Задача №3883. Противопожарная безопасность
В Якутске \(n\) домов. Некоторые из них соединены дорогами с односторонним движением.
В последнее время в Якутске участились случаи пожаров. В связи с этим жители решили построить в городе несколько пожарных станций. Но возникла проблема: едущая по вызову пожарная машина, конечно, может игнорировать направление движения текущей дороги, однако возвращающаяся с задания машина обязана следовать правилам дорожного движения (жители Якутска свято чтут эти правила!).
Ясно, что, где бы ни оказалась пожарная машина, у нее должна быть возможность вернуться на ту пожарную станцию, с которой выехала. Но строительство станций стоит больших денег, поэтому на совете города было решено построить минимальное количество станций таким образом, чтобы это условие выполнялось. Кроме того, для экономии было решено строить станции в виде пристроек к уже существующим домам.
Ваша задача — написать программу, рассчитывающую оптимальное положение станций.
В первой строке входного файла задано число \(n\) (\(1 \le n \le 3\,000\)). Во второй строке записано количество дорог \(m\) (\(1 \le m \le 100\,000\)). Далее следует описание дорог в формате \(a_i\) \(b_i\), означающее, что по \(i\)-й дороге разрешается движение автотранспорта от дома \(a_i\) к дому \(b_i\) (\(1 \le a_i, b_i \le n\)).
В первой строке выведите минимальное количество пожарных станций \(K\), которые необходимо построить. Во второй строке выведите \(K\) чисел в произвольном порядке — дома, к которым необходимо пристроить станции. Если оптимальных решений несколько, выведите любое.
5 7 1 2 2 3 3 1 2 1 2 3 3 4 2 5
2 5 4