#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define ld long double
#define pii pair<int, int>
#define f first
#define s second
#define boost() cin.tie(0), cin.sync_with_stdio(0)

const int MN = 600005;

int n, u, v, ans[MN], id[MN], col[MN], dist[MN];
vector<int> a[MN];

int32_t main() {
    boost();

    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 0; i < n * (1 << (n - 1)); i++) {
            cin >> u >> v;
            a[u].push_back(v);
            a[v].push_back(u);
            ans[i] = col[i] = id[i] = 0;
            dist[i] = -1;
        }
        dist[0] = 0;
        queue<int> q;
        for (int i = 0; i < n; i++) {
            int nxt = a[0][i];
            id[nxt] = 1 << i;
            q.push(nxt);
            dist[nxt] = 1;
        }
        while (q.size()) {
            int cur = q.front(); q.pop();
            for (int nxt : a[cur]) {
                if (dist[nxt] >= 0) {
                    if (dist[nxt] == dist[cur] + 1) id[nxt] |= id[cur];
                    continue;
                }
                id[nxt] |= id[cur];
                dist[nxt] = dist[cur] + 1;
                q.push(nxt);
            }
        }
        for (int i = 0; i < 1 << n; i++) a[i].clear();
        for (int i = 0; i < 1 << n; i++) ans[id[i]] = i;
        for (int i = 0; i < 1 << n; i++) printf("%lld ", ans[i]);
        printf("\n");
        if (__builtin_popcount(n) > 1) {printf("-1\n"); continue;}
        for (int i = 0; i < 1 << n; i++) {
            for (int j = 0; j < n; j++) if (i & (1 << j)) col[i] ^= j;
        }
        for (int i = 0; i < 1 << n; i++) printf("%lld ", col[id[i]]);
        printf("\n");
    }

    return 0;
}