// Author: Adrian Kuegel

import java.io.*;
import java.util.*;

public class adrian {
	public static void main(String [] args) throws Exception {
		// let adrian solve it ;-)
		(new adrian()).solve();
	}
	public void solve() throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int tc = Integer.parseInt(in.readLine());
		while(tc-- > 0) {
			StringTokenizer strtok = new StringTokenizer(in.readLine());
			int n = Integer.parseInt(strtok.nextToken());
			int m = Integer.parseInt(strtok.nextToken());
			int [][] requests = new int[2][m];
			for (int i=0; i<m; ++i) {
				strtok = new StringTokenizer(in.readLine());
				requests[0][i] = Integer.parseInt(strtok.nextToken());
				requests[1][i] = Integer.parseInt(strtok.nextToken());
			}
			int [] res = connect(1<<n, requests);
			for (int i=0; i<m; ++i)
				System.out.print(res[i] + (i < m-1? " ":"\n"));
		}
	}
	int [] connect(int N, int [][] requests) {
		int m = requests[0].length;
		if (m == 0)
			return null;
		int [] res = new int[m];
		if (N == 1)
			return res;
		int [][] used = new int[2][N];
		for (int i=0; i<N; ++i)
			used[0][i] = used[1][i]  = -1;
		for (int i=0; i<m; ++i) {
			used[0][requests[0][i]] = i;
			used[1][requests[1][i]] = i;
		}
		int [] len = new int[2];
		int [] which = new int[m];
		// handle paths
		for (int i=0; i<m; ++i) {
			int j = -1, cur = 0;
			if (used[0][(requests[0][i]+N/2)&(N-1)]<0)
				j = i;
			else if (used[1][(requests[1][i]+N/2)&(N-1)]<0) {
				j = i;
				cur = 1;
			}
			while (j >= 0 && which[j] == 0) {
				++len[cur];
				which[j] = cur + 1;
				cur = 1 - cur;
				j = used[cur][(requests[cur][j]+N/2)&(N-1)];
			}
		}
		// handle cycles
		for (int i=0; i<m; ++i) {
			int j = i, cur = 0;
			while (j >= 0 && which[j] == 0) {
				++len[cur];
				which[j] = cur + 1;
				cur = 1 - cur;
				j = used[cur][(requests[cur][j]+N/2)&(N-1)];
			}
		}
		N >>= 1;
		int [][] requests1 = new int[2][len[0]];
		int [][] requests2 = new int[2][len[1]];
		len[0] = len[1] = 0;
		for (int i=0; i<m; ++i)
			if (which[i] == 1) {
				requests1[0][len[0]] = requests[0][i] & (N-1);
				requests1[1][len[0]++] = requests[1][i] & (N-1);
			}
			else {
				requests2[0][len[1]] = requests[0][i] & (N-1);
				requests2[1][len[1]++] = requests[1][i] & (N-1);
			}
		int [] res1 = connect(N, requests1);
		int [] res2 = connect(N, requests2);
		len[0] = len[1] = 0;
		for (int i=0; i<m; ++i)
			if (which[i] == 1)
				res[i] = res1[len[0]++];
			else
				res[i] = N + res2[len[1]++];
		return res;
	}
}
