Nebius Welcome Round (Div. 1 + Div. 2) |
---|
Закончено |
Ада управляет сетью, состоящей из $$$n$$$ серверов и $$$m$$$ прямых соединений между ними. Каждое прямое соединение между парой различных серверов позволяет осуществлять двустороннюю передачу информации между этими двумя серверами. Ада знает, что с помощью этих $$$m$$$ прямых соединений возможна передача информации между любыми двумя серверами в этой сети (напрямую или через промежуточные серверы). Будем называть сервер $$$v$$$ соседом сервера $$$u$$$, если существует прямое соединение между этими двумя серверами.
Аде нужно настроить в своей сети WRP (Weird Routing Protocol — Странный протокол маршрутизации). Для каждого сервера $$$u$$$ ей нужно выбрать ровно одного соседа и назначить его вспомогательным сервером $$$a(u)$$$. Рассмотрим процесс того, как будет работать маршрутизация после определения всех $$$a(u)$$$. Предположим, сервер $$$u$$$ хочет найти путь до сервера $$$v$$$, отличного от $$$u$$$.
Как видите, эта процедура либо создает правильный путь и завершается, либо работает вечно. Таким образом, для Ады крайне важно правильно настроить 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
Название |
---|