// Author: Lukas Polacek
// Date: November 1, 2010
// Algorithm: Recursive coloring
// Complexity: O(nm)

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <stack>
#include <cstdio>
#include <bitset>
#include <cassert>
using namespace std;

#define rep(i,a,b) for(__typeof(b) i=a; i<(b); ++i)

typedef pair<int, int> pii;
typedef vector<int> vi;
vector<bool> seen[16], color[16];
void dfs(int l, vector<vi> &g, int lev, int offset, bool col)
{
    seen[lev][offset + l] = true;
    color[lev][offset + l] = col;
    rep(i,0,g[l].size())
        if (!seen[lev][offset + g[l][i]])
            dfs(g[l][i], g, lev, offset, !col);
}
void do_coloring(vi &a, vi &b, int lev, int offset)
{
    if (a.empty()) return;
    if (lev == 0)
    {
        color[0][offset + 1] = 1;
        return;
    }

    int pol = 1 << lev;
    vector<vi> f(pol);
    rep(i,0,a.size())
        f[b[i] % pol].push_back(a[i]);

    vector<vi> g(2 * pol);
    rep(i,0,f.size())
    {
        if (f[i].size() == 2)
        {
            g[f[i][0]].push_back(f[i][1]);
            g[f[i][1]].push_back(f[i][0]);
        }
        assert(f[i].size() <= 2);
    }
    rep(i,0,pol)
    {
        g[i].push_back(i | pol);
        g[i | pol].push_back(i);
    }

    rep(i,offset,offset+g.size())
        if (!seen[lev][i])
            dfs(i - offset, g, lev, offset, false);

    vi x[2], y[2];
    rep(i,0,a.size())
    {
        x[color[lev][offset + a[i]]].push_back(a[i] & (pol - 1));
        y[color[lev][offset + a[i]]].push_back(b[i] & (pol - 1));
    }
    rep(i,0,2)
        do_coloring(x[i], y[i], lev - 1, offset + pol * i);
}
int main()
{
    int t; scanf("%d", &t);
    while (t--)
    {
        int n, m;
        scanf("%d %d", &n, &m);

        vi a(m), b(m);
        rep(i,0,m)
            scanf("%d %d", &a[i], &b[i]);

        rep(i,0,n)
            seen[i] = color[i] = vector<bool>(1 << n, false);

        do_coloring(a, b, n - 1, 0);
        rep(i,0,a.size())
        {
            bitset<16> q(a[i]), w(b[i]);
            rep(j,0,n)
            {
                int lev = n - 1 - j;
                q[lev] = color[lev][q.to_ulong()];
            }
            if (i)
                printf(" ");
            printf("%d", q.to_ulong());
        }
        puts("");
    }
}
