Routing
Contest: Nebius Welcome Round (Div. 1 + Div. 2)
Difficulty rating: 2400
Tags: bitmasks, brute force, dfs and similar, dp, graphs

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.

Input format:
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.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
6 7
1 2
2 3
3 1
4 5
5 6
4 6
2 5

Example output:
Yes
2 5 2 5 2 5

Example input:
3 2
1 2
2 3

Example output:
Yes
2 1 2

Editorial:
A directed graph where each node has an out-degree equal to $$$1$$$ (exactly one arc starts at this node) is called functional. By setting auxiliary servers $$$a(v)$$$ for each server $$$v$$$ we define a functional graph.
The following condition is necessary and sufficient. The answer exists if and only if there exists a functional graph defined by $$$a(v)$$$ that contains a cycle $$$C$$$ such that $$$N_G(C) = V(G)$$$. That means that each node should be neighbouring to at least one node of this cycle in the original graph. Note that cycles of length $$$1$$$ are not allowed as $$$a(v) \ne v$$$ by definition. The proof is easy. If such a cycle $$$C$$$ exists we can reconstruct all other $$$a(v)$$$ to lead to this cycle. This will allow WRP to construct a path to each server after the procedure gets to the cycle. If such a cycle doesn't exists, we can pick any node of any cycle (functional graph always has at least one) and some servers will be unreachable from it.
Wow we need to find a cycle of length $$$\geq 2$$$ such that each server belongs to this cycle or is directly connected to at least one server of the cycle.
First we run a dynamic programming similar to Hamiltonian path and identify all the subsets of servers that can form a cycle. This will take $$$O(2^n \cdot n^2)$$$ if we use the following meaning of $$$d(m, v)$$$. $$$d(m, v) = 0$$$ if there exists a path that starts from node $$$u$$$, visits all nodes of a subset defined by bitmask $$$m$$$ and ends in node $$$v$$$. Here node $$$u$$$ is the node with minimum index in subset $$$m$$$, as you can always pick the minimum-indexed node as the beginning of the cycle.
After we compute $$$d(m, v)$$$ we take all $$$m$$$ such that there exists $$$d(m, v) = 1$$$ and check whether $$$N_G(m) = V(G)$$$. This can be done in $$$O(2^n \cdot n^2)$$$ as well.
Thus, the overall complexity is $$$O(2^n \cdot n^2)$$$.