The Final Pursuit Codeforces Solution

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.

See Also: Codeforces Round 730 (Div. 2)

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:The Final Pursuit Codeforces Solution

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 Final Pursuit Codeforces Solution

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

The Final Pursuit Codeforces Solution

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

#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[0] = 2;
	coord[0] = st;
	h[0] = 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();
}

Codeforces Round #730 (Div. 2)

July Long Challenge 2021 Solutions

Weekly Contest 247

Biweekly Contest 55

Codechef Long Challenge Solutions

June Long Challenge 2021 Solutions

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

February Long Challenge 2021

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

Leave a Comment

Please Click on 1 or 2 Ads to help us run this site.
+