eolymp
bolt
Try our new interface for solving problems
Məsələlər

Хакеры

Хакеры

В сети компании \textit{Melkosoft} \textbf{N} серверов, использующих операционную систему \textit{Losedows}. Некоторые из них соединены двусторонними каналами связи. Сеть называется \textit{надёжной}, если между двумя любыми различными серверами найдется какой-либо маршрут, состоящий из одного или нескольких каналов связи. Однако, сеть, в которой вообще нет серверов, надёжной не считается. Наши доблестные хакеры хотят наглядно продемонстрировать компании \textit{Melkosoft} ошибку в последней версии \textit{Losedows} (естественно, без согласия компании \textit{Melkosoft}). А именно, если в сети вырубить несколько серверов таким образом, что оставшаяся часть сети станет ненадёжной, то все оставшиеся серверы сети резко повисают. Так как бомбардировка сервера битыми пакетами таким образом, чтобы он вырубился - занятие крайне тяжёлое, то хакеры хотят вырубить минимально возможное число серверов таким образом, чтобы все остальные повисли. Напишите программу, которая определяет минимальное множество серверов, которые нужно бомбардировать. \InputFile В первой строке заданы два числа \textbf{N} и \textbf{M} (\textbf{1} ≤ \textbf{N} ≤ \textbf{50}, \textbf{0} ≤ \textbf{M} ≤ \textbf{100}). Далее следуют \textbf{M} строк, описывающие пары серверов, соединённые каналами связи. Каждый канал описывается строкой из двух чисел \textbf{u_i} \textbf{v_i}, где \textbf{1} ≤ \textbf{u_i}, \textbf{v_i} ≤ \textbf{N} - номера серверов, соединённых \textbf{i}-м каналом. Два сервера могут быть соединены более чем одним каналом. \OutputFile В первой строке выведите минимальное число серверов \textbf{K}, которое необходимо вырубить, чтобы все оставшиеся повисли из-за ошибки в \textit{Losedows}. Во второй строке выведите номера серверов, которые необходимо вырубить, в произвольном порядке. Если оптимальных решений несколько, разрешается выводить любое. Если исходная сеть\textit{Melkosoft} ненадёжна, выведите число \textbf{0}.
Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
Giriş verilənləri #1
1 0
Çıxış verilənləri #1
1
1