CF1804E Routing

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 $ ). 1. 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. 2. If the path was not found at the first step, server $ u $ asks its auxiliary server $ a(u) $ to find the path. 3. Auxiliary server $ a(u) $ follows this process starting from the first step. 4. 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 \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.

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.