CF1804E.Routing
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Ada operates a network that consists of n servers and m direct connections between them. Each direct connection between a pair of distinct servers allows bidirectional transmission of information between these two servers. Ada knows that these m direct connections allow to directly or indirectly transmit information between any two servers in this network. We say that server v is a neighbor of server u if there exists a direct connection between these two servers.
Ada needs to configure her network's WRP (Weird Routing Protocol). For each server u she needs to select exactly one of its neighbors as an auxiliary server a(u) . After all a(u) are set, routing works as follows. Suppose server u wants to find a path to server v (different from u ).
- Server u checks all of its direct connections to other servers. If it sees a direct connection with server v , it knows the path and the process terminates.
- If the path was not found at the first step, server u asks its auxiliary server a(u) to find the path.
- Auxiliary server a(u) follows this process starting from the first step.
- After a(u) finds the path, it returns it to u . Then server u constructs the resulting path as the direct connection between u and a(u) plus the path from a(u) to v .
As you can see, this procedure either produces a correct path and finishes or keeps running forever. Thus, it is critically important for Ada to configure her network's WRP properly.
Your goal is to assign an auxiliary server a(u) for each server u in the given network. Your assignment should make it possible to construct a path from any server u to any other server v using the aforementioned procedure. Or you should report that such an assignment doesn't exist.
输入格式
The first line of the input contains two integers n and m ( 2≤n≤20 , n−1≤m≤2n⋅(n−1) ) — the number of servers and the number of direct connections in the given network.
Then follow m lines containing two integers ui and vi ( 1≤ui,vi≤n , ui=vi ) each, the i -th line describes the i -th direct connection.
It is guaranteed that there is no more than one direct connection between any two servers. It is guaranteed that there is a direct or indirect route (consisting only of the given direct connections) between any two servers.
输出格式
If there is no way to assign an auxiliary server a(u) for each server u in such a way that WRP will be able to find a path from any server u to any other server v , print "No" in the only line of the output.
Otherwise, print "Yes" in the first line of the output. In the second line of the output print n integers, the i -th of these integers should be equal to a(i) – the index of the auxiliary server for server i . Do not forget that there must be a direct connection between server i and server a(i) .
You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
输入输出样例
输入#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