Unusual Graph
Contest: Kotlin Heroes: Episode 2
Difficulty rating: 3000
Tags: *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?

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

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Example input:
4 4
1 2
2 3
3 4
4 1

Example output:
0 1 0 1

Example input:
3 0

Example output:
0 0 0

Editorial:
Key lemma
• If two vertices have the same set of adjacent vertices, we can set them equal numbers.
Because if two vertices with the same adjacent vertices have different numbers, we can change any one of them to the other, and it is easy to see that all constraints will be satisfied.
So, we can merge all vertices with the equal adjacency list into one vertex, and reduce the problem to following:
New problem
• Set different integers $$$0 \leq a_v \leq 15$$$ to vertices of the graph with $$$n \leq 16$$$ vertices, to satisfy the same condition as in the original problem.
Solution 1 (Found by participants)
• You can use brute force with some prunings, and it will work fast enough. It can be proved that it will work fast enough. For example, it is quite clear that it will work fast enough if the number of edges is big because you can set $$$0,1,2,4,8$$$ arbitrary to vertex and its neighbors, and you will have $$$\leq 11$$$ remaining values to place, so it is quite clear that it is $$$\leq 11!$$$, and with further case analysis you can prove that it is way much faster.
Solution 2 (Intendend)
Now we can see that there are $$$\leq 2^{16}$$$ possible graphs, up to isomorphism.
So we can fix the set of values of vertices, and check that the given graph and the current graph are isomorphic.
Isomorphism problem
• You need to check that two graphs with $$$n \leq 16$$$ are isomorphic, note that these graphs are not arbitrary, so you can use some hacky way to check isomorphism.
Well, indeed, some hash-functions will work here! For example, you can fix some vertex as root, and calculate some hash of the graph with different coefficients of vertices, according to is it root or not. Also, you may fix more vertices, not only one root.
Any naive hash-function will reduce the number of candidate graphs to $$$\leq 300$$$.
For them, you can check with some smart, but slower to calculate hash-functions, as written earlier.
Bonus (maybe unsolvable?)
• Solve for $$$0 \leq a_v \leq 31$$$.