310246: CF1804E. Routing
Description
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.
InputThe first line of the input contains two integers $n$ and $m$ ($2 \leq n \leq 20$, $n - 1 \leq m \leq \frac{n \cdot (n - 1)}{2}$) — the number of servers and the number of direct connections in the given network.
Then follow $m$ lines containing two integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$, $u_i \ne v_i$) 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.
OutputIf 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.
ExamplesInput6 7 1 2 2 3 3 1 4 5 5 6 4 6 2 5Output
Yes 2 5 2 5 2 5Input
3 2 1 2 2 3Output
Yes 2 1 2Input
4 4 1 3 2 3 4 1 4 2Output
Yes 3 3 1 1Input
6 5 1 2 2 3 3 4 4 5 5 6Output
No
Input
题意翻译
给定一个 $n$ 个点 $m$ 条边的 **无向联通图** ，称 $y$ 是 $x$ 的邻居，当且仅当无向边 $(x,y)$ 存在。 你需要构造一个序列 $(a_1,\dots,a_n)$ ，满足： - 对于任意 $1\leq i\leq n$ ，无向边 $(i,a_i)$ 存在； - 对于任意 $x,y(x\neq y)$ ，初始时 $i$ 为 $x$ ，然后不断让 $i$ 变为 $a_i$ ，存在某个 $i$ ，使得 $y$ 是其一个邻居。 或报告无解。Output
E. 路由
有一个由n个服务器和m个直接连接构成的网络。每对不同的服务器之间的直接连接允许双向信息传输。对于每个服务器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≤n≤20，n−1≤m≤n(n−1)/2）——给定网络中的服务器数量和直接连接数量。
然后跟着m行，每行包含两个整数ui和vi（1≤ui,vi≤n，ui≠vi），第i行描述第i个直接连接。
保证任意两台服务器之间最多只有一个直接连接。保证任何两台服务器之间都存在由给定直接连接构成的直接或间接路径。
输出数据格式：
如果没有办法为每个服务器u分配一个辅助服务器a(u)，使得WRP能够找到从任何服务器u到任何其他服务器v的路径，则打印"No"。
否则，第一行打印"Yes"。在第二行打印n个整数，第i个整数应等于a(i)——服务器i的辅助服务器的索引。不要忘记服务器i和服务器a(i)之间必须有直接连接。
输出答案时大小写不敏感。例如，"yEs"、"yes"、"Yes"和"YES"都将被视为肯定回答。题目大意： E. 路由 有一个由n个服务器和m个直接连接构成的网络。每对不同的服务器之间的直接连接允许双向信息传输。对于每个服务器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≤n≤20，n−1≤m≤n(n−1)/2）——给定网络中的服务器数量和直接连接数量。 然后跟着m行，每行包含两个整数ui和vi（1≤ui,vi≤n，ui≠vi），第i行描述第i个直接连接。 保证任意两台服务器之间最多只有一个直接连接。保证任何两台服务器之间都存在由给定直接连接构成的直接或间接路径。 输出数据格式： 如果没有办法为每个服务器u分配一个辅助服务器a(u)，使得WRP能够找到从任何服务器u到任何其他服务器v的路径，则打印"No"。 否则，第一行打印"Yes"。在第二行打印n个整数，第i个整数应等于a(i)——服务器i的辅助服务器的索引。不要忘记服务器i和服务器a(i)之间必须有直接连接。 输出答案时大小写不敏感。例如，"yEs"、"yes"、"Yes"和"YES"都将被视为肯定回答。