1670E - Hemose on the Tree - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define ld long double
#define pii pair<int,int>
#define pdd pair<db,db>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,1,-1};
const double eps=1e-6; 
const int inf=1e9+7;
const int mod=998244353;
const int N=2e5+10,M=N<<1;
struct edge{
    int v,ne;
}e[M];
int h[N],idx;
void add(int a,int b){
    e[idx]={b,h[a]};
    h[a]=idx++;
}
int a[N],w[N];
int n,m;
void dfs(int u,int fa,int f){
    for(int i=h[u];~i;i=e[i].ne){
        int v=e[i].v;
        if(v==fa) continue;
        dfs(v,u,1-f);
        if(f==0) a[v]=m,w[i/2]=m+n;
        else a[v]=m+n,w[i/2]=m;
        m++;
    }
}
void solve(){
    cin>>n;
    int x,y;
    n=pow(2,n);
    m=1;idx=0;
    for(int i=1;i<=n;i++) h[i]=-1;
    for(int i=1;i<n;i++){
        cin>>x>>y;
        add(x,y),add(y,x);
    }
    a[1]=n;
    dfs(1,-1,0);
    cout<<1<<'\n';
    for(int i=1;i<=n;i++) cout<<a[i]<<' ';
    cout<<'\n';
    for(int i=0;i<n-1;i++) cout<<w[i]<<' ';
    cout<<'\n';
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie();cout.tie();
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}