// Problem: E. The Final Pursuit
// Contest: Codeforces - Codeforces Round #730 (Div. 2)
// URL: https://codeforces.com/contest/1543/problem/E
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//And in that light,I find deliverance.
#include<bits/stdc++.h>
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
vector<int> e[65536];
int vis[65536];
int id[65536],inv[65536];
int col[65536];
signed main()
{
	for(int T=read();T--;)
	{
		int n=read();
		int m=n*(1<<(n-1));
		int N=1<<n;
		for(int i=0; i<N; ++i) e[i].clear(),vis[i]=0,id[i]=0;
		for(int i=1; i<=m; ++i) 
		{
			int u=read(),v=read();
			e[u].push_back(v);
			e[v].push_back(u);
		}
		int visc=1;
		vector<int> cur,nxt;
#define pb push_back
		vis[0]=2;
		int powpowpow2=1;
		for(int i:e[0])
		{
			vis[i]=1,cur.pb(i),id[i]=powpowpow2,++visc;
			powpowpow2<<=1;
		}
		while(visc!=N)
		{
			nxt.clear();
			for(int i:cur) vis[i]=2;
			for(int i:cur) for(int j:e[i]) if(vis[j]!=2)
			{
				id[j]|=id[i];
				if(!vis[j]) vis[j]=1,++visc,nxt.pb(j);
			}
			cur=nxt;
		}
		for(int i=0; i<N; ++i) inv[id[i]]=i;
		for(int i=0; i<N; ++i) printf("%d ",inv[i]);
		puts(""); 
		int o=n;
		while(!(o&1)) o>>=1;
		if(o!=1) puts("-1");
		else
		{
			for(int i=0; i<N; ++i)
			{
				int s=0;
				for(int j=0; j<n; ++j) if(i&(1<<j)) s^=j;
				col[inv[i]]=s;
			}
			for(int i=0; i<N; ++i)
			{
				set<int> s;
				for(int j:e[i]) s.insert(col[j]);
				assert((int)s.size()==n);
			}
			for(int i=0; i<N; ++i) printf("%d ",col[i]);
			puts("");
		}
	}
	return 0;
}