← 返回题目列表

Codeforces · 1804/E

E. 路由

中文机器翻译题面 查看原题

Ada 运营的网络由 $$$n$$$ 服务器以及它们之间的 $$$m$$$ 直接连接组成。一对不同服务器之间的每个直接连接都允许在这两个服务器之间双向传输信息。 Ada 知道这些 $$$m$$$ 直接连接允许在该网络中的任何两个服务器之间直接或间接传输信息。如果服务器 $$$v$$$ 是服务器 $$$u$$$ 的邻居,如果这两个服务器之间存在直接连接。

Ada 需要配置其网络的 WRP(怪异路由协议)。对于每个服务器 $$$u$$$,她需要准确选择其邻居之一作为辅助服务器 $$$a(u)$$$。设置完所有 $$$a(u)$$$ 后,路由工作如下。假设服务器$$$u$$$想要找到到服务器$$$v$$$的路径(与$$$u$$$不同)。

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}$$$) - 给定网络中服务器的数量和直接连接的数量。

然后跟随包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \ne v_i$$$) 的 $$$m$$$ 行,第 $$$i$$$ 行描述第 $$$i$$$ 直接连接。

保证任意两台服务器之间不存在超过一个直接连接。保证任意两个服务器之间存在直接或间接路由(仅包含给定的直接连接)。

输出

如果无法为每个服务器 $$$u$$$ 分配一个辅助服务器 $$$a(u)$$$,以便 WRP 能够找到从任何服务器 $$$u$$$ 到任何其他服务器 $$$v$$$ 的路径,请在输出的唯一行中打印“No”。

否则,在输出的第一行打印“Yes”。在输出打印 $$$n$$$ 整数的第二行中,这些整数中的第 $$$i$$$ 应等于 $$$a(i)$$$ – 服务器 $$$i$$$ 的辅助服务器的索引。不要忘记服务器 $$$i$$$ 和服务器 $$$a(i)$$$ 之间必须有直接连接。

您可以在任何情况下输出答案(大写或小写)。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。

示例

输入 #1

6 7
1 2
2 3
3 1
4 5
5 6
4 6
2 5

输出 #1

Yes
2 5 2 5 2 5

输入 #2

3 2
1 2
2 3

输出 #2

Yes
2 1 2

输入 #3

4 4
1 3
2 3
4 1
4 2

输出 #3

Yes
3 3 1 1

输入#4

6 5
1 2
2 3
3 4
4 5
5 6

输出#4

No