#include <bits/stdc++.h>

using namespace std;

int t, n, col[(1<<16)];
vector<int> g[(1<<16)], perm;

void solve(vector<int> & cur) {
    int cs = cur.size();
    if(cs == 1) {
        perm.push_back(cur[0]);
        return;
    }
    vector<bool> in_cur, which_half, vis;
    vector<int> nxt, lower_half;
    for(int i = 0; i<(1<<n); i++) {
        in_cur.push_back(false);
        which_half.push_back(false);
        vis.push_back(false);
        nxt.push_back(0);
    }
    for(int i = 0; i<cs; i++) {
        in_cur[cur[i]] = true;
        vis[i] = false;
    }
    int init1 = cur[0], init2;
    for(int i: g[init1]) {
        if(in_cur[i]) {
            init2 = i;
        }
    }
    queue<int> q;
    q.push(init1), q.push(init2);
    vis[init1] = vis[init2] = true;
    which_half[init1] = false, which_half[init2] = true;
    nxt[init1] = init2, nxt[init2] = init1;
    while(!q.empty()) {
        int x = q.front();
        q.pop();
        if(!which_half[x]) {
            lower_half.push_back(x);
        }
        for(int i: g[x]) {
            if(in_cur[i]) {
                if(!vis[i]) {
                    which_half[i] = which_half[x];
                    q.push(i);
                    vis[i] = true;
                }
                if(vis[i] && (which_half[i]^which_half[x])) {
                    nxt[x] = i, nxt[i] = x;
                }
            }
        }
    }
    solve(lower_half);
    for(int i = 0; i<lower_half.size(); i++) {
        perm.push_back(nxt[perm[i]]);
    }
}

int main() {
    cin >> t;
    while(t--) {
        cin >> n;
        for(int i = 0, u, v; i < (n * (1<<(n-1))); i++) {
            cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        vector<int> cur;
        for(int i = 0; i<(1<<n); i++) {
            cur.push_back(i);
        }
        solve(cur);
        for(int p: perm) {
            cout << p << " ";
        }
        cout << endl;
        set<int> pow2;
        for(int i = 1; i <= 16; i *= 2) {
            pow2.insert(i);
        }
        if(!pow2.count(n)) {
            cout << -1 << endl;
        } else {
            for(int i = 0; i < (1<<n); i++) {
                for(int j = 0; j < n; j++) {
                    if(i & (1<<j)) {
                        col[perm[i]] ^= j;
                    }
                }
            }
            for(int i = 0; i<(1<<n); i++) {
                cout << col[i] << " ";
                col[i] = 0;
            }
            cout << endl;
        }
        perm.clear();
        for(int i = 0; i<(1<<n); i++) {
            g[i].clear();
        }
    }
}
