//#pragma GCC optimize ("O3", "unroll-loops")
//#pragma GCC target ("avx2")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define LL long long
#define PII pair<int, int>
#define PLL pair<LL, LL>
#define all_of(v) (v).begin(), (v).end()
#define sort_unique(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define fi first
#define se second
const int MAXN = 17;
const int MAXV = 1 << MAXN;
//const LL INF = (LL) 1e9 + 8763;
//const LL MOD = (LL) 998244353;
using namespace std;
template <class T> using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <class T> using max_heap = priority_queue<T, vector<T>, less<T>>;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// function<vector<int>(int, int, int)> func = [&] (int m, int l, int c) {};

int n, vn, en, id[MAXV], pos[MAXV], col[MAXV], act[MAXV], act2[MAXV], vis[MAXV];
vector<int> G[MAXV];

void dfs(vector<int> V, int dim, int code) {
//	cout << "AT " << dim << '\n';
//	for (int v : V) {
//		cout << v << ' ';
//	}
//	cout << '\n';
	if (dim == 1) {
		pos[V[0]] = (code);
		pos[V[1]] = (code | 1);
		id[code] = V[0];
		id[code | 1] = V[1];
		return;
	}
	for (int v : V) {
		act[v] = 1;
		vis[v] = 0;
	}
	
	int r1 = V[0], r2 = -1;
	queue<PII> Q;
	for (int to : G[r1]) if (act[to]) r2 = to;
	Q.push(PII(r1, r2));
	vis[r1] = vis[r2] = 1;
	vector<int> V1, V2;
	while (!Q.empty()) {
		PII p = Q.front(); Q.pop();
		int v1 = p.fi, v2 = p.se;
		V1.push_back(v1);
		V2.push_back(v2);
		for (int to : G[v1]) if (act[to]) act2[to] = 1;
		for (int to : G[v2]) {
			if (!act[to] || vis[to]) continue;
			int ok = 0;
			for (int to2 : G[to]) {
				if (!act2[to2] || vis[to2]) continue;
				vis[to] = vis[to2] = 1;
				Q.push(PII(to2, to));
				ok = 1;
				break;
			}
			assert(ok);
		}
		for (int to : G[v1]) act2[to] = 0;
	}
	
	for (int v : V) {
		act[v] = vis[v] = 0;
	}
	
	dfs(V1, dim - 1, code);
	for (int i = 0; i < V2.size(); i++) {
		int v1 = V1[i], v2 = V2[i], code = pos[v1] | 1 << (dim - 1);
		pos[v2] = code;
		id[code] = v2;
	}
}

void phase1() {
	// id, pos
	vector<int> V;
	for (int i = 0; i < vn; i++) {
		V.push_back(i);
	}
	dfs(V, n, 0);
}

void phase2() {
	for (int i = 0; i < vn; i++) {
		for (int j = 0; j < n; j++) {
			if (i >> j & 1) {
				col[i] ^= j;
			}
		}
	}
}

void solve() {
	cin >> n;
	vn = (1 << n), en = n * vn / 2;
	for (int i = 0; i < vn; i++) {
		id[i] = pos[i] = col[i] = act[i] = act2[i] = vis[i];
		G[i].clear();
	}
	for (int i = 0; i < en; i++) {
		int u, v;
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	
	phase1();
	for (int i = 0; i < vn; i++) {
		cout << id[i] << " \n"[i + 1 == vn];
	}
	
	if (n != 1 && n != 2 && n != 4 && n != 8 && n != 16) {
		cout << "-1\n";
		return;
	}
	phase2();
	for (int i = 0; i < vn; i++) {
		cout << col[pos[i]] << " \n"[i == vn - 1];
	}
}

int main() {
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
	ios_base::sync_with_stdio(0); cin.tie(0);

	int tc = 1;
	cin >> tc;
	for (int i = 1; i <= tc; i++) {
		solve();
	}

	return 0;
}