// Author: Adrian Kuegel
// Algorithm: divide and conquer, greedy matching
// Complexity: O( m * n )
// Date: May 19th, 2010

#include <stdio.h>
#include <assert.h>
#include <algorithm>
using namespace std;

#define MAXK 16
#define MAXN (1<<MAXK)

struct Switch {
	int *inp, *out, *ind, m;
	Switch(int M): m(M) {
		inp = new int[M];
		out = new int[M];
		ind = new int[M];
	}
	~Switch() {
		delete [] inp;
		delete [] out;
		delete [] ind;
	}
};

char out[MAXN][MAXK + 1];
int mark[MAXN];

// follow a path in bipartite graph and assign edges to the two switches S1 and S2 alternatingly
void followPath(int curi, int *link1, int *link2, Switch &S1, Switch &S2, const Switch &S, int k, char c) {
	if (curi < 0)
		return;
	S1.inp[S1.m] = S.inp[curi];
	S1.out[S1.m] = S.out[curi];
	S1.ind[S1.m++] = S.ind[curi];
	out[S.ind[curi]][k] = c;
	int next = link1[curi];
	link1[curi] = link2[curi] = -2;
	followPath(next, link2, link1, S2, S1, S, k, '1'-c+'0');
}

// mark critical node pairs which can be assigned to the same input/output
void mark_critical(int *e, int m, int n, int *link) {
	int t, other;
	for (int i=0; i<m; ++i) {
		t = e[i] % n;
		other = (t + n/2) % n;
		if (!mark[other]) {
			assert(mark[t] == 0);
			mark[t] = i + 1;
			link[i] = -1;
		}
		else {
			other = mark[other] - 1;
			assert(link[other] == -1);
			link[other] = i;
			link[i] = other;
		}
	}
	for (int i=0; i<m; ++i)
		mark[e[i]%n] = 0;
}

void solve(int curk, const Switch &S) {
	if (S.m == 0)
		return;
	if (curk == 0) {
		assert(S.m == 1);
		return;
	}
	int *link1 = new int[S.m];
	int *link2 = new int[S.m];
	mark_critical(S.inp, S.m, 1<<curk, link1);
	mark_critical(S.out, S.m, 1<<curk, link2);
	Switch S1(S.m), S2(S.m);
	S1.m = S2.m = 0;
	for (int i=0; i<S.m; ++i) {
		// first handle paths starting on left side
		if (link2[i] == -1)
			followPath(i, link1, link2, S1, S2, S, curk, '0');
		// handle paths starting on right side
		else if (link1[i] == -1)
			followPath(i, link2, link1, S2, S1, S, curk, '1');
	}
	// now handle cycles
	for (int i=0; i<S.m; ++i) {
		if (link2[i] < 0)
			continue;
		assert(link1[i] >= 0);
		// remove last edge from the cycle
		link2[link2[i]] = -2;
		// now handle remaining path
		followPath(i, link1, link2, S1, S2, S, curk, '0');
	}
	assert(S1.m + S2.m == S.m);
	solve(curk-1, S1);
	solve(curk-1, S2);
	delete [] link1;
	delete [] link2;
}

int main() {
	int tc, k, n, m;
	scanf("%d", &tc);
	assert(tc <= 100);
	while(tc--) {
		scanf("%d %d", &k, &m);
		assert(k > 0 && k <= MAXK && m >= 1 && m <= (1<<k));
		n = 1 << k;
		Switch S(m);
		for (int i=0; i<m; ++i) {
			scanf("%d %d", &S.inp[i], &S.out[i]);
			assert(S.inp[i] >= 0 && S.inp[i] < n && S.out[i] >= 0 && S.out[i] < n);
			S.ind[i] = i;
		}
		solve(k, S);
		for (int i=0; i<m; ++i) {
			int num = 0;
			for (int j=k; j>0; --j)
				num = num * 2 + (out[i][j]-'0');
			if (i)
				printf(" ");
			printf("%d", num);
		}
		puts("");
	}
	return 0;
}
