B. Округлая планарность
Задан неориентированный граф. Потребуем, чтобы все его вершины располагались в точках некоторой окружности, а ребра соответствовали хордам окружности. Нужно проверить - возможно ли расположить вершины таким образом, чтобы ребра не пересекались.
Входные данные
В первой строке входного файла содержится число вершин графа N (1≤N≤50) и число ребер M. В последующих M строках заданы ребра, каждое номерами двух вершин.
Выходные данные
|
В первой строке выходного файла должно находиться слово Yes, если граф можно расположить заданным образом, или No, если нет. |
| Если граф можно расположить, то во второй строке выдать последовательность номеров вершин в порядке обхода по окружности. |
Пример входного и выходного файлов
| INPUT.TXT |
OUTPUT.TXT |
3 3
1 2
2 3
1 3
|
Yes
1 2 3
|