The Final Pursuit
Contest: Codeforces Round 730 (Div. 2)
Difficulty rating: 2700
Tags: bitmasks, constructive algorithms, divide and conquer, graphs, greedy, math

Finally, you have defeated Razor and now, you are the Most Wanted street racer. Sergeant Cross has sent the full police force after you in a deadly pursuit. Fortunately, you have found a hiding spot but you fear that Cross and his force will eventually find you. To increase your chances of survival, you want to tune and repaint your BMW M3 GTR.

The car can be imagined as a permuted $$$n$$$-dimensional hypercube. A simple $$$n$$$-dimensional hypercube is an undirected unweighted graph built recursively as follows:

- Take two simple $$$(n-1)$$$-dimensional hypercubes one having vertices numbered from $$$0$$$ to $$$2^{n-1}-1$$$ and the other having vertices numbered from $$$2^{n-1}$$$ to $$$2^{n}-1$$$. A simple $$$0$$$-dimensional Hypercube is just a single vertex.
- Add an edge between the vertices $$$i$$$ and $$$i+2^{n-1}$$$ for each $$$0\leq i < 2^{n-1}$$$.

A permuted $$$n$$$-dimensional hypercube is formed by permuting the vertex numbers of a simple $$$n$$$-dimensional hypercube in any arbitrary manner.

Examples of a simple and permuted $$$3$$$-dimensional hypercubes are given below:

Note that a permuted $$$n$$$-dimensional hypercube has the following properties:

- There are exactly $$$2^n$$$ vertices.
- There are exactly $$$n\cdot 2^{n-1}$$$ edges.
- Each vertex is connected to exactly $$$n$$$ other vertices.
- There are no self-loops or duplicate edges.

Let's denote the permutation used to generate the permuted $$$n$$$-dimensional hypercube, representing your car, from a simple $$$n$$$-dimensional hypercube by $$$P$$$. Before messing up the functionalities of the car, you want to find this permutation so that you can restore the car if anything goes wrong. But the job isn't done yet.

You have $$$n$$$ different colours numbered from $$$0$$$ to $$$n-1$$$. You want to colour the vertices of this permuted $$$n$$$-dimensional hypercube in such a way that for each and every vertex $$$u$$$ satisfying $$$0\leq u < 2^n$$$ and for each and every colour $$$c$$$ satisfying $$$0\leq c < n$$$, there is at least one vertex $$$v$$$ adjacent to $$$u$$$ having a colour $$$c$$$. In other words, from each and every vertex, it must be possible to reach a vertex of any colour by just moving to an adjacent vertex.

Given the permuted $$$n$$$-dimensional hypercube, find any valid permutation $$$P$$$ and colouring.

Input format:
The first line of input contains a single integer $$$t$$$ ($$$1\leq t\leq 4096$$$) — the number of test cases.

For each test case, the first line contains a single integer $$$n$$$ ($$$1\leq n\leq 16$$$).

Each of the next $$$n\cdot 2^{n-1}$$$ lines contain two integers $$$u$$$ and $$$v$$$ ($$$0\leq u, v < 2^n$$$) denoting that there is an edge between the vertices numbered $$$u$$$ and $$$v$$$.

It is guaranteed that the graph described in the input is a permuted $$$n$$$-dimensional hypercube.

Additionally, it is guaranteed that the sum of $$$2^n$$$ over all test cases does not exceed $$$2^{16}=65\,536$$$.

Output format:
For each test case, print two lines.

In the first line, output any permutation $$$P$$$ of length $$$2^n$$$ that can be used to transform a simple $$$n$$$-dimensional hypercube to the permuted $$$n$$$-dimensional hypercube given in the input. Two permuted hypercubes are considered the same if they have the same set of edges. If there are multiple answers, output any of them.

In the second line, print the colouring. If there is no way to colour the vertices satisfying the conditions, output $$$-1$$$. Otherwise, output a single line containing $$$2^n$$$ space separated integers. The $$$i$$$-th integer must be the colour of the vertex numbered $$$(i-1)$$$ in the permuted $$$n$$$-dimensional hypercube. If there are multiple answers, output any of them.

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

Note:
The colouring and the permuted hypercube for the first test case is shown below:

The colouring and the permuted hypercube for the second test case is shown below:

The permuted hypercube for the third test case is given in the problem statement. However, it can be shown that there exists no way to colour that cube satifying all the conditions. Note that some other permutations like $$$[0, 5, 7, 3, 1, 2, 4, 6]$$$ and $$$[0, 1, 5, 2, 7, 4, 3, 6]$$$ will also give the same permuted hypercube.

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

Example output:
0 1
0 0
0 1 3 2
0 0 1 1
5 3 0 7 2 6 1 4
-1

Editorial:
Before moving to the solution, notice a very important property of simple $$$n$$$-Dimensional Hypercubes - Two vertices $$$a$$$ and $$$b$$$ are connected if and only if $$$a$$$ and $$$b$$$ differ by exactly one bit in their binary representations.
Part 1 - Building the permutation $$$p$$$
The following greedy strategy works - Choose any arbitrary vertex as $$$p_0$$$. Then find $$$p_u$$$ for all $$$u$$$ in increasing order from $$$1$$$ to $$$2^n-1$$$. To find $$$p_u$$$, first find a set $$$S$$$ of all the vertices $$$p_v$$$ such that $$$u$$$ and $$$v$$$ differ by exactly one bit and $$$v < u$$$. Then find a vertex $$$w$$$ connected to all the vertices in this set and which hasn't been used in the permutation yet and assign $$$p_u=w$$$. Now, let's see why this works.
I claim that during each step while finding $$$p_u$$$, if $$$u$$$ is not a power of $$$2$$$ then there will only be at most one vertex $$$w$$$ satisfying all the conditions. To prove this, let's assume that a vertex $$$w$$$ is connected to two different vertices $$$a$$$ and $$$b$$$ in a simple hypercube. Then, $$$a$$$ and $$$w$$$ differ by exactly one bit and also $$$b$$$ and $$$w$$$ differ by exactly one bit. Moreover, these bits must be different otherwise $$$a=b$$$. So, it follows that $$$a$$$ and $$$b$$$ differ by exactly $$$2$$$ bits. We have four cases to consider -
1. $$$a$$$ = $$$...0...0...$$$ and $$$b$$$ = $$$...1...1...$$$ where the dots represent the same bits. Then $$$w$$$ can be either $$$...0...1...$$$ or $$$...1...0...$$$. But since we are finding $$$p_u$$$ in increasing order, both of these have been already used. So, we don't consider this case.
2. $$$a$$$ = $$$...1...1...$$$ and $$$b$$$ = $$$...0...0...$$$ where the dots represent the same bits. Then $$$w$$$ can be either $$$...0...1...$$$ or $$$...1...0...$$$. But, again, since we are finding $$$p_u$$$ in increasing order, both of these have been already used. So, we don't consider this case either.
3. $$$a$$$ = $$$...0...1...$$$ and $$$b$$$ = $$$...1...0...$$$ where the dots represent the same bits. Then $$$w$$$ can be either $$$...0...0...$$$ or $$$...1...1...$$$. But only the second option is possible because we are finding $$$p_u$$$ in increasing order. So, there is only one possible unused vertex.
4. $$$a$$$ = $$$...1...0...$$$ and $$$b$$$ = $$$...0...1...$$$ where the dots represent the same bits. Then $$$w$$$ can be either $$$...0...0...$$$ or $$$...1...1...$$$. But only the second option is possible because we are finding $$$p_u$$$ in increasing order. So, there is only one possible unused vertex.
Thus, we have shown that there are exactly two vertices in a simple hypercube that are connected to two fixed vertices $$$a$$$ and $$$b$$$ and out of them, at most one may be unused. Since a permuted hypercube is derived from a simple hypercube and its structure is the same, at each step while finding $$$p_u$$$, if $$$u$$$ is not a power of $$$2$$$, for each pair of numbers $$$(v_1,v_2)$$$ such that $$$p_{v_1}$$$ and $$$p_{v_2}$$$ belongs to $$$S$$$, there will be exactly one vertex $$$w$$$ connected to both $$$p_{v_1}$$$ and $$$p_{v_2}$$$. So, we have no choice rather than to choose this vertex as $$$p_u$$$.
The only case left to consider is when $$$u$$$ is a power of $$$2$$$. In such cases, the set $$$S$$$ will contain only $$$1$$$ vertex that is $$$p_0$$$. So, there are many possible choices for the vertex $$$w$$$. But it turns out that any of them may be chosen because in such cases, we start a new dimension of the hypercube and it doesn't matter in which direction we add that dimension.
Part 2 - Colouring the Hypercube
This is the interesting part of the solution. Let's try to colour a simple $$$n$$$-Dimensional Hypercube rather than the permuted one. Then, we can again permute the vertices using the permutation we found in the first part to get a colouring for the permuted cube.
I claim that if $$$n$$$ is not a power of $$$2$$$, then no colouring exists. A simple explanation is that the graph is symmetric and also the colours. So, it is natural that the number of vertices of each colour must be equal meaning $$$2^n$$$ must be divisible by $$$n$$$ or in other words, $$$n$$$ must be a power of $$$2$$$ itself. But if symmetry doesn't satisfy you, I have a formal proof too.
Proof - According to the condition, every vertex must be connected to at least one vertex of every colour or equivalently, exactly one vertex of every colour since there are $$$n$$$ colours and $$$n$$$ neighbours of each vertex. So, if we consider the set of neighbours of any vertex, every colour will appear exactly once in that set. If we consider the set of neighbours of all vertices, every colour will appear $$$2^n$$$ times in that set. But every vertex has been counted $$$n$$$ times in that set because a particular vertex is the neighbour of $$$n$$$ other vertices. So, if we consider the set of all vertices, every colour will appear $$$\frac{2^n}{n}$$$ times in that set. Obviously, this number must be a whole number. So, $$$2^n$$$ must be divisible by $$$n$$$ or in other words, $$$n$$$ must itself be a power of $$$2$$$ for a colouring to exist. Otherwise, it doesn't exist. To show that a colouring exists if $$$n$$$ is a power of $$$2$$$, we will construct a colouring.
Construction - Consider the binary equivalent of each vertex. Define the least significant bit (LSB) as the $$$0$$$-th bit and the most significant bit (MSB) as the $$$(n-1)$$$-th bit. Let $$$b_i$$$ denote the $$$i$$$-th bit. Then, the colour of a vertex is given by $$$\bigoplus\limits_{i=0}^{n-1} i\cdot b_i$$$. Let's see why this works.
• $$$\bigoplus\limits_{i=0}^{n-1} i\cdot b_i$$$ will always lie between $$$0$$$ and $$$n-1$$$ inclusive because $$$n$$$ is a power of $$$2$$$.
• If we are at a vertex $$$u$$$ with a colour $$$c_1$$$ and we want to reach a vertex of colour $$$c_2$$$, we can reach the vertex $$$v=u\oplus(1\ll (c_1\oplus c_2))$$$. This is a vertex adjacent to $$$u$$$ since it differs from it by exactly $$$1$$$ bit and this is the $$$(c_1\oplus c_2)$$$-th bit. Notice that the colour of this vertex will be $$$c_1\oplus (c_1\oplus c_2) = c_2$$$.
• $$$(c_1\oplus c_2)$$$ will always lie between $$$0$$$ and $$$n-1$$$ because $$$n$$$ is a power of $$$2$$$. So, $$$v$$$ will always be a valid vertex number.
You can see that many of these facts break when $$$n$$$ is not a power of $$$2$$$. So, this colouring will not work in such cases.
Finally, after colouring the simple hypercube, we need to restore the vertex numbers of the permuted hypercube. This can be simply done by replacing all vertices $$$u$$$ with $$$p_u$$$ using the permutation we found in Part 1.
Well, that's enough of theoretical stuff. For those who like visualising things, here is a 4-D Hypercube and its colouring -
Time Complexity - The permutation can be found in $$$\mathcal{O}(2^n\cdot n\cdot \log n)$$$ if we implement the adjacency list representation of the permuted hypercube using sets or $$$\mathcal{O}(2^n\cdot n^2)$$$ if implemented using vectors. The colouring can be constructed in $$$\mathcal{O}(2^n\cdot n)$$$. The colouring can be restored for the permuted hypercube in $$$\mathcal{O}(2^n)$$$. So, the total time complexity is $$$\mathcal{O}(2^n\cdot n\cdot \log n)$$$ or $$$\mathcal{O}(2^n\cdot n^2)$$$ depending upon the implementation.