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