# The Final Pursuit Codeforces Solution

Page Contents

## The Final Pursuit Solution

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 nn-dimensional hypercube. A simple nn-dimensional hypercube is an undirected unweighted graph built recursively as follows:

• Take two simple (n−1)(n−1)-dimensional hypercubes one having vertices numbered from 00 to 2n−1−12n−1−1 and the other having vertices numbered from 2n−12n−1 to 2n−12n−1. A simple 00-dimensional Hypercube is just a single vertex.
• Add an edge between the vertices ii and i+2n−1i+2n−1 for each 0≤i<2n−10≤i<2n−1.

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

Examples of a simple and permuted 33-dimensional hypercubes are given below: Note that a permuted nn-dimensional hypercube has the following properties:

• There are exactly 2n2n vertices.
• There are exactly n⋅2n−1n⋅2n−1 edges.
• Each vertex is connected to exactly nn other vertices.
• There are no self-loops or duplicate edges.

Let’s denote the permutation used to generate the permuted nn-dimensional hypercube, representing your car, from a simple nn-dimensional hypercube by PP. 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 nn different colours numbered from 00 to n−1n−1. You want to colour the vertices of this permuted nn-dimensional hypercube in such a way that for each and every vertex uu satisfying 0≤u<2n0≤u<2n and for each and every colour cc satisfying 0≤c<n0≤c<n, there is at least one vertex vv adjacent to uu having a colour cc. 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 nn-dimensional hypercube, find any valid permutation PP and colouring.Input

The first line of input contains a single integer tt (1≤t≤40961≤t≤4096) — the number of test cases.

For each test case, the first line contains a single integer nn (1≤n≤161≤n≤16).

Each of the next n⋅2n−1n⋅2n−1 lines contain two integers uu and vv (0≤u,v<2n0≤u,v<2n) denoting that there is an edge between the vertices numbered uu and vv.

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

Additionally, it is guaranteed that the sum of 2n2n over all test cases does not exceed 216=65536216=65536.Output

For each test case, print two lines.

In the first line, output any permutation PP of length 2n2n that can be used to transform a simple nn-dimensional hypercube to the permuted nn-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−1. Otherwise, output a single line containing 2n2n space separated integers. The ii-th integer must be the colour of the vertex numbered (i−1)(i−1) in the permuted nn-dimensional hypercube. If there are multiple answers, output any of them.

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
```

output

```0 1
0 0
0 1 3 2
0 0 1 1
5 3 0 7 2 6 1 4
-1
```

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][0,5,7,3,1,2,4,6] and [0,1,5,2,7,4,3,6][0,1,5,2,7,4,3,6] will also give the same permuted hypercube.

## Solution

Program C++:

```#include <locale.h>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <iterator>
#include <sstream>
#include <map>
#include <math.h>
#include <stdio.h>
#include <stack>
#include <random>
#include <ctime>
#include <queue>
#include <set>
using namespace std;
using ld = long double;
using ll = long long;

ll mod = 1e9 + 7;

ld eps = 1e-5;

ll bpow(ll a, ll p) {
ll res = 1;
while (p > 0) {
if (p % 2) {
res *= a;
res %= mod;
}
a *= a;
a %= mod;
p /= 2;
}
return res;
}

ll inv(ll a) {
return bpow(a, mod - 2);
}

ll gcd(ll a, ll b) {
if (!b) return a;
return gcd(b, a % b);
}

ll kek(vector<int> x) {
ll ans = 0;
for (int i = 0; i < x.size(); i++) {
ans += x[i] * (1 << i);
}
return ans;
}

vector<int> perminv(vector<int> perm) {
int n = perm.size();
vector<int> ans(n);
for (int i = 0; i < n; i++) {
ans[perm[i]] = i;
}
return ans;
}

void solve() {
int n;
cin >> n;
int k = (1 << n);
vector<vector<int>> g(k);
for (int i = 0; i < n * k / 2; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}

vector<vector<int>> coord(k, vector<int>(n));
vector<int> st(n, 0);
queue<int> q;
vector<int> used(k, 0);
vector<int> h(k, -1);

used = 2;
coord = st;
h = 0;
q.push(0);
int num = 0;

while (!q.empty()) {
int u = q.front();
q.pop();
for (auto v : g[u]) {
if (used[v] == 0) {
q.push(v);
coord[v] = coord[u];
used[v] = 1;
h[v] = h[u] + 1;
if (h[v] == 1) {
coord[v][num] = 1;
num++;
used[v] = 2;
}
}
else if (used[v] == 1 && h[v] == h[u] + 1) {
for (int i = 0; i < n; i++) {
if (coord[u][i] == 1 && coord[v][i] == 0) coord[v][i] = 1;
used[v] = 2;
}
}

}

}

vector<int> perm(k);
for (int i = 0; i < k; i++) {
perm[i] = kek(coord[i]);
}
perm = perminv(perm);

for (int i = 0; i < k; i++) {
cout << perm[i] << ' ';
}

cout << '\n';

int a = 0;
int b = n;
while (n > 1) {
if (n % 2 == 1) {
cout << -1 << '\n';
return;
}
else
{
n /= 2;
a++;
}
}

vector<int> truecolor(k / 2);

for (int i = 0; i < k / 2; i++) {
truecolor[i] = i % n;
}

vector<int> coloring(k);

for (int i = 0; i < k; i++) {
coloring[perm[i]] = truecolor[i];
}
for (int i = 0; i < k; i++) {
cout << coloring[i] << ' ';
}
cout << '\n';

}

int main()
{
cout.precision(100);
int t;
cin >> t;
while (t--)
solve();
}```