Республиканская олимпиада по информатике, 2012 год, 9 класс
(Клуб читателей)
В клубе состоят $N$ человек. Каждый месяц выходит новая книга, и Вы рассылаете ее членам клуба. Так как покупать всем по книге выйдет очень дорого, Вы можете разослать книги только определенным читателям. Читатели, получившие книгу снимают с нее несколько копий и рассылают всем своим хорошим знакомым в клубе. Читатели, получившие копию книги, делают то же самое. Если читатель $A$ является хорошим знакомым читателя $B,$ это не означает, что $B$ является хорошим знакомым $A.$
Вам известны все хорошие знакомые каждого читателя. Определите минимальное количество экземпляров книги, которое необходимо приобрести и отправить, чтобы все читатели клуба получили бы книгу или ее копию.
посмотреть в олимпиаде
Ограничение по времени:
2 секунды
Ограничение по памяти:
64 мегабайта
В клубе состоят $N$ человек. Каждый месяц выходит новая книга, и Вы рассылаете ее членам клуба. Так как покупать всем по книге выйдет очень дорого, Вы можете разослать книги только определенным читателям. Читатели, получившие книгу снимают с нее несколько копий и рассылают всем своим хорошим знакомым в клубе. Читатели, получившие копию книги, делают то же самое. Если читатель $A$ является хорошим знакомым читателя $B,$ это не означает, что $B$ является хорошим знакомым $A.$
Вам известны все хорошие знакомые каждого читателя. Определите минимальное количество экземпляров книги, которое необходимо приобрести и отправить, чтобы все читатели клуба получили бы книгу или ее копию.
Формат входного файла
В первой строке входного файла задаются два целых числа $N$ и $M$ $(1 \le N \le 10000,$ $1 \le M \le 100000).$ В следующих $M$ строка задаются по два целых числа $A$ и $B:$ читатель с номером $B$ — хороший знакомый читателя с номером $A$ $(1 \le A, B \le N,$ $A \ne B).$ Числа в строках разделены пробелами.
Формат выходного файла
В первой строке выходного файла выведите минимальное количество экземпляров книги, которое необходимо отправить. Во второй строке — номера читателей, которые должны их получить. Если вариантов несколько, выведите любой.
Примеры:
Вход 5 5 1 2 1 3 3 1 2 4 5 4Ответ
2 5 3Вход
5 4 1 2 3 2 2 4 2 5Ответ
2 3 1
Комментарий/решение:
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.