#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <random>
#include <chrono>
#define all(v) (v).begin(), (v).end()
#define unq(v) (v).erase(unique(all(v)), (v).end())
#define vec vector
#define pii pair <int, int>
#define pli pair <ll, int>
#define pil pair <int, ll>
#define pll2 pair <ll, ll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define MULTI int T; cin >> T; while(T--)
#define sqr(x) ((x) * (x))
#define yesno(x) cout << ((x) ? "Yes" : "No") << endl
#define test cerr << '!' << endl;
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

void main0 ();
int main () {
	clock_t start, end;
	#ifndef ONLINE_JUDGE
		freopen("C:\\Users\\98497\\Desktop\\code\\file.in", "r", stdin);
		start = clock();
	#endif
	ios::sync_with_stdio(false); cin.tie(0);
	main0();
	#ifndef ONLINE_JUDGE
		end = clock();
		cout << "( " << (end - start) << " ms )" << endl;
		fclose(stdin);
	#endif
	return 0;
}

const int dx[8] = {0, 1, -1, 0, 1, 1, -1, -1};
const int dy[8] = {1, 0, 0, -1, 1, -1, -1, 1};
const int N = 2e5 + 5;
const int M = 1e5;
const int INF = 0x3f3f3f3f;
const ll INFF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-6;
const double Pi = acos(-1.0);
mt19937 rnd((unsigned int) chrono::steady_clock::now().time_since_epoch().count());

int n;

vector <int> e[N];
int vis[N], inq[N];
int p[N], col[N];
int ansp[N], anscol[N];

void main0 () {
	MULTI {
		cin >> n;
		for (int i = 0;i <= (1 << n) - 1;++i) {
			e[i].clear();
			vis[i] = inq[i] = 0;
			p[i] = col[i] = 0;
		}
		
		int dcnt = 0;
		queue <int> q;
		for (int i = 1;i <= n * (1 << (n - 1));++i) {
			int u, v;
			cin >> u >> v;
			e[u].pb(v);
			e[v].pb(u);
			if (u > v) swap(u, v);
			if (u == 0) {
				p[v] = (1 << (dcnt++));
				q.push(v);
			}
		}
		
		p[0] = 0;
		vis[0] = 1;
		while (q.size()) {
			int u = q.front(); q.pop();
			vis[u] = 1;
			for (int v : e[u]) if (!vis[v]) {
				if (!inq[v]) inq[v] = 1, q.push(v);
				p[v] |= p[u];
			}
		}
		
		col[0] = 0;
		for (int i = 0;i <= n - 1;++i) {
			for (int j = 0;j <= (1 << i) - 1;++j) {
				col[j + (1 << i)] = col[j] ^ i;
			}
		}
		
		for (int i = 0;i <= (1 << n) - 1;++i) {
			ansp[p[i]] = i;
			anscol[i] = col[p[i]];
		}
		for (int i = 0;i <= (1 << n) - 1;++i) {
			cout << ansp[i] << ' ';
		}
		cout << endl;
		if (__builtin_popcount(n) == 1) {
			for (int i = 0;i <= (1 << n) - 1;++i) {
				cout << anscol[i] << ' ';
			}
			cout << endl;
		} else {
			cout << -1 << endl;
		}
	}
}