#include<bits/stdc++.h>
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define rep(i,a,b) for(i=(a);i<=(b);++i)
#define per(i,a,b) for(i=(a);i>=(b);--i)
#define REP(i,a,b) for(i=(a);i< (b);++i)
#define PER(i,a,b) for(i=(a);i> (b);--i)
#define ERR(...) fprintf(stderr,__VA_ARGS__)
template<class T>inline void cmn(T &x,const T &a){if(a<x)x=a;}
template<class T>inline void cmx(T &x,const T &a){if(x<a)x=a;}
template<class T>inline bool bmn(T &x,const T &a){if(a<x){x=a;return true;}else return false;}
template<class T>inline bool bmx(T &x,const T &a){if(x<a){x=a;return true;}else return false;}
template<class T>inline T gcd(const T &a,const T &b){
	if(a&&b){
		T x=a,y=b;
		for(;;){
			if(!(x%=y))return y;
			if(!(y%=x))return x;
		}
	}else return a|b;
}

const int MAXN=65536;
vector<int>E[MAXN];
inline int findtwo(const vector<int> &L,const vector<int> &R){
	bool fi=false;int Xor;
	vector<int>::const_iterator l=L.begin(),r=R.begin();
	for(;;){
		if((*l)==(*r)){
			if(fi)return Xor^(*l);
			else{fi=true;Xor=(*(l++));++r;}
		}else if((*l)<(*r))++l;else ++r;
	}
}
int P[MAXN],Ans[MAXN],Ans1[2],Ans2[4],Ans4[16],Ans8[256],AnsH[65536];
bool Odd[MAXN];
inline void expand(int *AnsL,int *AnsR,const int &N){
	int i,j,a,N2=(1<<N),*AnsRI;
	REP(i,0,N2){
		a=Odd[i]?(AnsL[i]|N):AnsL[i];
		AnsRI=AnsR+(i<<N);
		REP(j,0,N2)AnsRI[j]=a^AnsL[j];
	}
}
inline void fillAnswer(int *AnsT,const int &N){
	int i;
	//REP(i,0,N)ERR("%d ",AnsT[i]);ERR("AnsT N=%d\n",N);
	REP(i,0,N)Ans[P[i]]=AnsT[i];
	REP(i,0,N)printf("%d ",Ans[i]);puts("");
}
#define HighBit(x) ((x)&((x)-1))
signed main(){
#ifdef ONLINE_JUDGE
	//freopen("problemname.in","r",stdin);
	//freopen("problemname.out","w",stdout);
#endif
	int T,N,N2,i,v,u,b;
	REP(i,1,65536)Odd[i]=!Odd[HighBit(i)];
	expand(Ans1,Ans2,1);
	expand(Ans2,Ans4,2);
	expand(Ans4,Ans8,4);
	expand(Ans8,AnsH,8);
	scanf("%d",&T);
	while(T--){
		scanf("%d",&N);
		per(v,(N2=(1<<N))-1,0)E[v].clear();
		b=1;
		per(i,(N<<N)>>1,1){
			scanf("%d%d",&v,&u);
			if(v){if(!u){P[b]=v;b<<=1;}}else{P[b]=u;b<<=1;}
			E[v].push_back(u);
			E[u].push_back(v);
		}
		REP(i,0,N2)sort(E[i].begin(),E[i].end());
		REP(i,3,N2)if(v=HighBit(i)){
			u=(HighBit(v)|(v^i));
			//ERR("i=%d v=%d u=%d\n",i,v,u);
			P[i]=(findtwo(E[P[v]],E[P[u]])^P[v&u]);
		}
		REP(i,0,N2)printf("%d ",P[i]);puts("");
		switch(N){
			case  1:fillAnswer(Ans1,2    );break;
			case  2:fillAnswer(Ans2,4    );break;
			case  4:fillAnswer(Ans4,16   );break;
			case  8:fillAnswer(Ans8,256  );break;
			case 16:fillAnswer(AnsH,65536);break;
			default:puts("-1");
		}
	}
	return 0;
}