E. Маршрутизация
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ада управляет сетью, состоящей из $$$n$$$ серверов и $$$m$$$ прямых соединений между ними. Каждое прямое соединение между парой различных серверов позволяет осуществлять двустороннюю передачу информации между этими двумя серверами. Ада знает, что с помощью этих $$$m$$$ прямых соединений возможна передача информации между любыми двумя серверами в этой сети (напрямую или через промежуточные серверы). Будем называть сервер $$$v$$$ соседом сервера $$$u$$$, если существует прямое соединение между этими двумя серверами.

Аде нужно настроить в своей сети WRP (Weird Routing Protocol — Странный протокол маршрутизации). Для каждого сервера $$$u$$$ ей нужно выбрать ровно одного соседа и назначить его вспомогательным сервером $$$a(u)$$$. Рассмотрим процесс того, как будет работать маршрутизация после определения всех $$$a(u)$$$. Предположим, сервер $$$u$$$ хочет найти путь до сервера $$$v$$$, отличного от $$$u$$$.

  • Сервер $$$u$$$ смотрит на все свои прямые соединения с другими серверами. Если он видит прямое соединение с сервером $$$v$$$, он знает путь и процесс завершается.
  • Если путь не был найден на первом шаге, сервер $$$u$$$ запрашивает поиск пути у своего вспомогательного сервера $$$a(u)$$$.
  • Вспомогательный сервер $$$a(u)$$$ следует этому процессу, начиная с первого шага.
  • После того, как $$$a(u)$$$ находит путь, он возвращает его $$$u$$$. Затем сервер $$$u$$$ строит результирующий путь как объединение прямого соединения между $$$u$$$ и $$$a(u)$$$ и пути от $$$a(u)$$$ до $$$v$$$.

Как видите, эта процедура либо создает правильный путь и завершается, либо работает вечно. Таким образом, для Ады крайне важно правильно настроить WRP своей сети.

Ваша цель — назначить вспомогательный сервер $$$a(u)$$$ для каждого сервера $$$u$$$ в данной сети таким образом, чтобы WRP мог построить путь от любого сервера $$$u$$$ к любому другому серверу $$$v$$$, используя вышеупомянутую процедуру. Или же требуется определить, что такое назначение вспомогательных серверов невозможно.

Входные данные

Первая строка входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \leq n \leq 20$$$, $$$n - 1 \leq m \leq \frac{n \cdot (n - 1)}{2}$$$) — количество серверов и количество прямых соединений в данной сети.

Далее следуют $$$m$$$ строк, содержащих по два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \ne v_i$$$), $$$i$$$-я строка описывает $$$i$$$-е прямое соединение.

Гарантируется, что между любыми двумя серверами существует не более одного прямого соединения. Гарантируется, что существует прямой или непрямой маршрут (состоящий только из заданных прямых соединений) между любыми двумя серверами.

Выходные данные

Если нет возможности назначить вспомогательный сервер $$$a(u)$$$ для каждого сервера $$$u$$$ таким образом, чтобы WRP смог найти путь от любого сервера $$$u$$$ к любому другому серверу $$$v$$$, выведите «No» в единственной строке вывода.

В противном случае выведите «Yes» в первой строке вывода. Во второй строке выведите $$$n$$$ целых чисел, $$$i$$$-е из которых должно быть равно $$$a(i)$$$ – номеру вспомогательного сервера для сервера $$$i$$$. Не забывайте, что должно быть прямое соединение между сервером $$$i$$$ и сервером $$$a(i)$$$.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Примеры
Входные данные
6 7
1 2
2 3
3 1
4 5
5 6
4 6
2 5
Выходные данные
Yes
2 5 2 5 2 5
Входные данные
3 2
1 2
2 3
Выходные данные
Yes
2 1 2
Входные данные
4 4
1 3
2 3
4 1
4 2
Выходные данные
Yes
3 3 1 1
Входные данные
6 5
1 2
2 3
3 4
4 5
5 6
Выходные данные
No