#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i,j,k) for(int i=j;i<=k;++i)
#define g(i,j,k) for(int i=j;i>=k;--i)
int n,m,s,l;
const int N=1e5;
int p[N],u[N],v[N],w[N],x,y,z;
vector<int>q[N];
queue<int>Q;
void dfs(int x,int y){
	if(v[x])return;u[x]=y;v[x]=1;
	f(t,0,m-1)dfs(x^(1<<t),y^t);
}
inline void doing(){
	cin>>m;n=1<<m;z=0;
	f(i,0,n)u[i]=v[i]=w[i]=0,q[i].clear(); 
	f(i,1,n*m/2){
		cin>>x>>y;
		q[x].push_back(y);
		q[y].push_back(x);
	}
	for(Q.push(0);Q.size();Q.pop()){
		u[x=Q.front()]=1;p[w[x]]=x;
		for(int y:q[x])if(!u[y]){
			w[y]|=w[x]?w[x]:1<<z++;
			if(!v[y])Q.push(y),v[y]=1;
		}
	}
	f(i,0,n-1)printf("%lld ",p[i]);
	puts("");
	if(n%m)return puts("-1"),void();
	f(i,0,n)u[i]=v[i]=0;dfs(0,0);
	f(i,0,n-1)printf("%lld ",u[w[i]]);
	puts("");
}
signed main(){
	int t;
	cin>>t;
	while(t--)doing();
	return 0;
}