I. Unusual Graph
*special; graphs
Ivan on his birthday was presented with array of non-negative integers \(a_1, a_2, \ldots, a_n\). He immediately noted that all \(a_i\) satisfy the condition \(0 \leq a_i \leq 15\).Ivan likes graph theory very much, so he decided to transform his sequence to the graph.There will be \(n\) vertices in his graph, and vertices \(u\) and \(v\) will present in the graph if and only if binary notations of integers \(a_u\) and \(a_v\) are differ in exactly one bit (in other words, \(a_u \oplus a_v = 2^k\) for some integer \(k \geq 0\). Where \(\oplus\) is Bitwise XOR).A terrible thing happened in a couple of days, Ivan forgot his sequence \(a\), and all that he remembers is constructed graph!Can you help him, and find any sequence \(a_1, a_2, \ldots, a_n\), such that graph constructed by the same rules that Ivan used will be the same as his graph?
The first line of input contain two integers \(n,m\) (\(1 \leq n \leq 500, 0 \leq m \leq \frac{n(n-1)}{2}\)): number of vertices and edges in Ivan's graph.Next \(m\) lines contain the description of edges: \(i\)-th line contain two integers \(u_i, v_i\) (\(1 \leq u_i, v_i \leq n; u_i \neq v_i\)), describing undirected edge connecting vertices \(u_i\) and \(v_i\) in the graph.It is guaranteed that there are no multiple edges in the graph. It is guaranteed that there exists some solution for the given graph.
Output \(n\) space-separated integers, \(a_1, a_2, \ldots, a_n\) (\(0 \leq a_i \leq 15\)). Printed numbers should satisfy the constraints: edge between vertices \(u\) and \(v\) present in the graph if and only if \(a_u \oplus a_v = 2^k\) for some integer \(k \geq 0\).It is guaranteed that there exists some solution for the given graph. If there are multiple possible solutions, you can output any.