CF1804E Routing

Ada 管理着一个由 $n$ 台服务器和 $m$ 条直接连接组成的网络。每一对不同服务器之间的直接连接都允许这两台服务器之间进行双向信息传输。Ada 已知，这 $m$ 条直接连接保证了网络中任意两台服务器之间都可以直接或间接地传递信息。我们称服务器 $v$ 是服务器 $u$ 的邻居，如果这两台服务器之间存在一条直接连接。 Ada 需要为她的网络配置 WRP（Weird Routing Protocol，奇怪路由协议）。对于每台服务器 $u$，她需要为其选择恰好一台邻居作为辅助服务器 $a(u)$。所有 $a(u)$ 设置好后，路由过程如下。假设服务器 $u$ 想要找到一条到服务器 $v$（$u \ne v$）的路径： 1. 服务器 $u$ 检查它与其他服务器的所有直接连接。如果发现与服务器 $v$ 的直接连接，则找到路径，过程结束。 2. 如果第一步未找到路径，服务器 $u$ 会请求其辅助服务器 $a(u)$ 去寻找路径。 3. 辅助服务器 $a(u)$ 从第一步开始重复该过程。 4. 当 $a(u)$ 找到路径后，将其返回给 $u$。然后服务器 $u$ 构造最终路径，即 $u$ 与 $a(u)$ 之间的直接连接，加上 $a(u)$ 到 $v$ 的路径。 如你所见，这一过程要么能正确找到路径并结束，要么会无限循环。因此，Ada 必须正确配置网络的 WRP。 你的目标是为给定网络中的每台服务器 $u$ 指定一个辅助服务器 $a(u)$。你的分配应保证，使用上述过程，任意服务器 $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$ 条直接连接。 保证任意两台服务器之间至多有一条直接连接。保证任意两台服务器之间都存在仅由这些直接连接组成的直接或间接路径。

如果不存在一种为每台服务器 $u$ 分配辅助服务器 $a(u)$ 的方式，使得 WRP 能够从任意服务器 $u$ 到达任意其他服务器 $v$，则输出一行 "No"。 否则，第一行输出 "Yes"。第二行输出 $n$ 个整数，第 $i$ 个整数为服务器 $i$ 的辅助服务器编号 $a(i)$。注意，服务器 $i$ 与 $a(i)$ 之间必须存在直接连接。 答案的大小写任意。例如，"yEs"、"yes"、"Yes" 和 "YES" 都会被识别为肯定回答。

由 ChatGPT 4.1 翻译