#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <set>
#include <vector>

using namespace std;
typedef long long ll;
const ll maxm=100010;
ll n,m;
ll p[maxm];
bool used[maxm];
set<ll> s[maxm];
vector<ll> adj[maxm];
void permuteHypercube()
{
	memset(p,-1,sizeof(p));
	memset(used,false,sizeof(used)); 
	p[0]=0;
	used[0]=true;
	for(ll u=1;u<m;u++)
	{
		vector<ll> req;
		for(ll i=0;i<n;i++)//找到在simple中直接相连的点，从大到小 
		{
			ll v=u^(1<<i);
			if(v<u)//因为只有比它小的才已经完成了编号 
				req.push_back(v);
		}
        ll v=req[0];
		for(ll i=0;i<adj[p[v]].size();i++)
		{
			ll w=adj[p[v]][i];
			if(used[w])
				continue;
			if(req.size()==1 || s[w].find(p[req[1]])!=s[w].end())
			{
				p[u]=w;
				used[w]=true;
				break;
			}
		}
    }
}
int main()
{
	ll T;
	scanf("%lld",&T);
	while(T--)
	{
		for(ll i=0;i<maxm;i++)
			adj[i].clear(),s[i].clear();
		scanf("%lld",&n);
		m=(1<<n);
		for(ll i=0;i<n*m/2;i++)
		{
			ll u,v;
			scanf("%lld%lld",&u,&v);
			adj[u].push_back(v);
			adj[v].push_back(u);
			s[u].insert(v);
			s[v].insert(u);
		}
		permuteHypercube();
		for(ll i=0;i<m;i++)
			printf("%lld ",p[i]);
		printf("\n");
		if(n!=1 && n!=2 && n!=4 && n!=8 && n!=16)
		{
			printf("-1\n");
			continue;
		}
		ll temp[m];
		for(ll i=0;i<m;i++)
		{
			ll clr=0;
			for(ll j=0;j<n;j++)
				if(i&(1<<j))
					clr=clr^j;
			temp[i]=clr;
		}
		ll c[m];
		for(ll i=0;i<m;i++)
			c[p[i]]=temp[i];
		for(ll i=0;i<m;i++)
			printf("%lld ",c[i]);
		printf("\n");
	}
}