#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <bitset>
#include <algorithm>
#include <climits>
using namespace std;
typedef long long ll;
const int N=2e5+10;
int t,p,n;
vector<int> g[N];
int res1[N],cnt=0;
map<pair<int,int>,int > res2;
pair<int,int> P[N];
void dfs(int x,int fa,int val){
for(int i=0;i<g[x].size();i++){
int to=g[x][i];
if(to==fa) continue;
if(val==n){
res2[{to,x}]=res2[{x,to}]=cnt+n;
res1[to]=cnt;
}else{
res2[{to,x}]=res2[{x,to}]=cnt;
res1[to]=cnt+n;
}
++cnt;
dfs(to,x,val^n);
}
}
int main(){
scanf("%d",&t);
while(t--){
cnt=1;
scanf("%d",&p);n=(1<<p);
for(int i=1;i<=(1<<p);i++) g[i].clear();
for(int i=1;i<(1<<p);i++){
int u,v;scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
P[i]={u,v};
}
res1[1]=n;
dfs(1,-1,n);
cout<<1<<endl;
for(int i=1;i<=n;i++) printf("%d ",res1[i]);puts("");
for(int i=1;i<n;i++){
printf("%d ",res2[P[i]]);
}puts("");
}
}
|
