|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Задача 13-2. Банкет
| Имя входного файла | input.txt |
| Имя выходного файла | output.txt |
| Максимальное время работы на одном тесте: | 1 секунда |
На банкет были приглашены N Очень Важных Персон (ОВП). Были поставлены 2 стола. Столы достаточно большие, чтобы все посетители банкета могли сесть за любой из них. Проблема заключается в том, что некоторые ОВП не ладят друг с другом и не могут сидеть за одним столом. Вас попросили определить, возможно ли всех ОВП рассадить за двумя столами.
Формат входных данных
В первой строке входного файла дано два числа: N и M
(1 <= N,M <= 100), где N - количество ОВП,
а M - количество пар ОВП, которые не могут сидеть
за одним столом. В следующих M строках записано по
2 числа - пары ОВП, которые не могут сидеть за
одним столом.
Формат выходных данных
Если способ рассадить ОВП существует, то в выходной файл выведите
YES в первой строке и номера ОВП, которых необходимо
посадить за первый стол, во второй строке. В противном
случае в первой и единственной строке выведите NO.
Пример
| input.txt | output.txt |
3 2 1 2 1 3 |
YES 2 3 |