#include <bits/stdc++.h>

#define IL __inline__ __attribute__((always_inline))

#define For(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++ i)
#define FOR(i, a, b) for (int i = (a), i##end = (b); i < i##end; ++ i)
#define Rep(i, a, b) for (int i = (a), i##end = (b); i >= i##end; -- i)
#define REP(i, a, b) for (int i = (a) - 1, i##end = (b); i >= i##end; -- i)

typedef long long LL;

template <class T>
IL bool chkmax(T &a, const T &b) {
  return a < b ? ((a = b), 1) : 0;
}

template <class T>
IL bool chkmin(T &a, const T &b) {
  return a > b ? ((a = b), 1) : 0;
}

template <class T>
IL T mmax(const T &a, const T &b) {
  return a > b ? a : b;
}

template <class T>
IL T mmin(const T &a, const T &b) {
  return a < b ? a : b;
}

template <class T>
IL T mabs(const T &a) {
  return a > 0 ? a : -a;
}

const int INF = 0X3F3F3F3F;
const double EPS = 1E-8, PI = acos(-1.0);

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define OK DEBUG("Passing [%s] in LINE %d...\n", __FUNCTION__, __LINE__)
#define SZ(x) ((int)(x).size())

const int MAXN = 100000 + 5, MAXM = 20 + 5;

int col[MAXM][MAXN];

IL void init() {
  for (int i = 2; i <= 16; i <<= 1) {
    int t = 1 << (i / 2);
    FOR(j, 0, t) {
      int f = (__builtin_popcount(j) & 1) * (i / 2), g = col[i / 2][j];
      FOR(k, 0, t) {
        int p = (j << (i / 2)) + k;
        col[i][p] = (col[i / 2][k] + g) % (i / 2) + f;
      }
    }
  }
}

std::vector<int> edge[MAXN];
std::queue<int> q;
int p[MAXN], fp[MAXN], num[MAXN], vis[MAXN], to[MAXN], cnt;

void work(const std::vector<int> &cur) {
  int s = SZ(cur);
  if (s == 1) {
    p[0] = cur.back();
    return;
  }
  ++ cnt;
  for (auto &x: cur) {
    num[x] = cnt;
    vis[x] = 0;
  }
  int k1 = cur[0], k2 = 0;
  for (auto &x: edge[k1]) {
    if (num[x] == cnt) {
      k2 = x;
      break;
    }
  }
  vis[k1] = 1, vis[k2] = 2;
  q.push(k1), q.push(k2);
  std::vector<int> tmp, ap;
  while (!q.empty()) {
    int t = q.front();
    q.pop();
    (vis[t] == 1 ? tmp : ap).push_back(t);
    for (auto &x: edge[t]) {
      if (num[x] == cnt && !vis[x]) {
        vis[x] = vis[t];
        q.push(x);
      } else if (num[x] == cnt && vis[x] == 1 && vis[t] == 2) {
        to[t] = x;
      }
    }
  }
  work(tmp);
  for (auto &x: ap) {
    fp[x] = fp[to[x]] + s / 2;
    p[fp[x]] = x;
  }
}

int main() {
  init();
  int _;
  scanf("%d", &_);
  for (; _; -- _) {
    int n;
    scanf("%d", &n);
    std::vector<int> tmp;
    FOR(i, 0, 1 << n) {
      edge[i].clear();
      tmp.push_back(i);
    }
    FOR(i, 0, n * (1 << (n - 1))) {
      int u, v;
      scanf("%d%d", &u, &v);
      edge[u].push_back(v);
      edge[v].push_back(u);
    }
    work(tmp);
    FOR(i, 0, 1 << n) {
      printf("%d ", p[i]);
    }
    puts("");
    if (__builtin_popcount(n) > 1) {
      puts("-1");
    } else {
      FOR(i, 0, 1 << n) {
        printf("%d ", col[n][fp[i]]);
      }
      puts("");
    }
  }
  return 0;
}
