#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pci pair <char, int>
#define pld pair <ld, ld>
#define ppld pair <pld, pld>
#define ppll pair <pll, pll>
#define pldl pair <ld, ll>
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define fastmap gp_hash_table
#define cd complex <double>
#define vcd vector <cd>
#define PI 3.14159265358979
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
bool vis[66005];
vector <ll> adj[66005];
ll cnt[66005];
ll perm[66005];
ll col[66005];
void solve(){
	ll n; cin >> n;
	for (ll i = 0; i < (1LL << n); i++){
		adj[i].clear();
		vis[i] = 0;
		col[i] = 0;
		perm[i] = 0;
	}
	for (ll i = 0; i < n * (1LL << (n - 1)); i++){
		ll u, v; cin >> u >> v;
		adj[u].eb(v); adj[v].eb(u);
	}
	perm[0] = 0;
	vis[0] = 1;
	for (ll i = 0; i < n; i++){
		perm[1LL << i] = adj[0][i];
		vis[perm[1LL << i]] = 1;
	}
	for (ll i = 1; i < (1LL << n); i++){
		if (perm[i]) continue;
		ll s = __builtin_popcountll(i);
		for (ll bit = 0; bit < n; bit++){
			if ((i >> bit) & 1){
				ll j = perm[i ^ (1LL << bit)];
				for (auto k : adj[j]){
					if (vis[k]) continue;
					cnt[k]++;
				}
			}
		}
		for (ll bit = 0; bit < n; bit++){
			if ((i >> bit) & 1){
				ll j = perm[i ^ (1LL << bit)];
				for (auto k : adj[j]){
					if (vis[k]) continue;
					if (cnt[k] == s) perm[i] = k;
					cnt[k]--;
				}
			}
		}
		vis[perm[i]] = 1;
		assert(perm[i]);
	}
	for (ll i = 0; i < (1LL << n); i++) cout << perm[i] << " ";
	cout << "\n";
	ll p2 = 1;
	while (p2 < n) p2 *= 2;
	if (p2 != n){
		cout << -1 << "\n"; return;
	}
	for (ll i = 0; i < (1LL << n); i++){
		for (ll bit = 0; bit < n; bit++){
			if ((i >> bit) & 1) col[perm[i]] ^= bit;
		}
	}
	for (ll i = 0; i < (1LL << n); i++) cout << col[i] << " ";
	cout << "\n";
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	ll t; cin >> t;
	while (t--) solve();
}