Задача №929. Четный граф
Неориентированный граф называется четно-нечетным, если найдутся две его вершины, между которыми существуют пути как из четного, так и из нечетного числа ребер. Напишите программу, которая:
- определяет, является ли заданный граф четно-нечетным;
- в случае отрицательного ответа на пункт 1 находит максимальное подмножество \(X\) вершин графа такое, что для любых двух вершин \(i\) и \(j\) из \(X\) выполняется следующее условие: все пути между \(i\) и \(j\) состоят из четного числа ребер.
Первая строка входного файла содержит число вершин графа \(N\) (\(1 \le N \le 100\)) и число ребер \(M\) (\(1 \le M \le 1\,000\)), а каждая последующая — пару чисел \((i, j)\), означающих, что в графе присутствует ребро, соединяющее вершины с номерами \(i\) и \(j\).
Первая строка выходного файла должна содержать ответ на пункт 1 в форме «YES/NO». В случае отрицательного ответа на пункт 1 вторая строка должна содержать количество вершин в множестве \(X\), а третья — номера вершин из этого множества в порядке возрастания, записанные через пробел. Если вариантов решений несколько, то достаточно вывести любое из них.
3 1 1 2
NO 2 2 3