#include<bits/stdc++.h>
using namespace std;
void GetPermute(int n,int m,vector<int> adj[],set<int> s[],int p[]){
	memset(p,-1,sizeof(p));
	p[0]=0;//define the initial vertex as 0
	bool used[m];
	memset(used,0,sizeof(used));
	used[0]=true;
	for(int u=1;u<m;u++){
		//find the vertex v that v<u and the difference between u and v is one bit
		vector<int>req;
		for(int i=0;i<n;i++){
			int v=u^(1<<i);
			if(v<u)
				req.push_back(v);
		}
		if(req.size()==1){
			//u equal to a pow of 2
			int v=req[0];
			for(int i=0;i<adj[p[v]].size();i++){
				int w=adj[p[v]][i];
				if(used[w])
					continue;
				p[u]=w;
				used[w]=true;
				break;
			}
		}
		else{
			int v=req[0];
			for(int i=0;i<adj[p[v]].size();i++){
				int w=adj[p[v]][i];
				if(used[w])
					continue;
				if(s[w].find(p[req[1]])!=s[w].end()){
					p[u]=w;
					used[w]=true;
					break;
				}
			}
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); 
	int t;cin>>t;
	while(t--){
		int n;cin>>n;
		int m=(1<<n);
		int p[m];
		vector<int>e[m];
		set<int>s[m];
		for(int i=1;i<=n*m/2;i++){
			int a,b;cin>>a>>b;
			e[a].push_back(b);
			e[b].push_back(a);
			s[a].insert(b);
			s[b].insert(a);
		}
		GetPermute(n,m,e,s,p);
		for(int i=0;i<m;i++)cout<<p[i]<<" ";cout<<endl;
		if(n!=1 && n!=2 && n!=4 && n!=8 && n!=16){
			cout<<-1<<endl;
			continue;
		}
		int temp[m];
		for(int i=0;i<m;i++){
			int clr=0;
			for(int j=0;j<n;j++){
				if(i&(1<<j))
					clr=clr^j;
			}
			temp[i]=clr;
		}
		int c[m];
		for(int i=0;i<m;i++)c[p[i]]=temp[i];
		for(int i=0;i<m;i++)cout<<c[i]<<" ";cout<<endl;
	}
}