#include <stdio.h>
#include <assert.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>

#define MAXK (16)
#define MAXN (1<<MAXK)
#define ACC 0
#define WA 1

int e[MAXN], a[MAXN], num[MAXN], testcase, k, m;
char visit[MAXN][MAXK * 2], path[MAXN][2 * MAXK + 1];
FILE *in, *out;

void exit_wa(const char *message) {
	printf("testcase %i: ",testcase);
	puts(message);
	// write the test case for which program fails to fail.in
	FILE *fail = fopen("fail.in", "w");
	if (fail == NULL)
		fprintf(stderr, "could not open fail.in, cannot write current test case\n");
	else {
		fprintf(fail, "1\n%d %d\n", k, m);
		for (int i=0; i<m; ++i)
			fprintf(fail, "%d %d\n", e[i], a[i]);
		fclose(fail);
	}
	fclose(in);
	fclose(out);
	exit(WA);
}

// mark the node in row "row" and column "col" to be visited
void set_visit(int row, int col) {
	// if it is already marked, the paths are not node-disjoint
	if (visit[row][col]) {
		char buf[100];
		sprintf(buf, "not node-disjoint paths, row = %d, column = %d", row, col);
		exit_wa(buf);
	}
	visit[row][col] = 1;
}

int main(int argc, char **argv) {
	// judge input
	in = fopen(argv[1], "r");
	if (in == NULL) {
		fprintf(stderr, "fatal error: could not open judge input at %s\n", argv[1]);
		exit(1);
	}
	// contestant output
	out = fopen(argv[3], "r");
	if (out == NULL) {
		fprintf(stderr, "fatal error: could not open judge output at %s\n", argv[2]);
		exit(1);
	}
	int tc, n;
	fscanf(in, "%d", &tc);
	for (testcase=1; testcase<=tc; ++testcase) {
		// first read the test case from the judge input
		fscanf(in, "%d %d", &k, &m);
		assert(k > 0 && k <= MAXK);
		n = 1 << k;
		for (int i=0; i<m; ++i) {
			fscanf(in, "%d %d", &e[i], &a[i]);
			assert(e[i] >= 0 && e[i] < n);
			assert(a[i] >= 0 && a[i] < n);
		}
		// set the array of visited nodes to 0
		// checking for node-disjoint paths implies edges are disjoint, too
		for (int i=0; i<n; ++i)
			memset(visit[i], 0, 2*k);
		char c;
		// read the contestant input and just verify if the numbers are between 0 and n-1
		for (int i=0; i<m; ++i) {
			num[i] = 0;
			c = fgetc(out);
			// the following characters should describe a connection path
			// the number must be between 0 and n-1
			do {
				if (c < '0' || c > '9') {
					char buf[100];
					sprintf(buf, "wrong character, digit expected, got %c\n", c);
					exit_wa(buf);
				}
				num[i] = num[i] * 10 + (c - '0');
				if (num[i] >= n) {
					char buf[100];
					sprintf(buf, "switch number too big: got %d, at most %d allowed\n", num[i], n-1);
					exit_wa(buf);
				}
				c = fgetc(out);
			}while(!isspace(c));
			if (i < m-1 && c != ' ') {
				char buf[100];
				sprintf(buf, "expected whitespace character, got character with ascii code %d\n", c);
				exit_wa(buf);
			}
			else if (i == m-1 && c != '\n') {
				char buf[100];
				sprintf(buf, "expected newline character, got character with ascii code %d\n", c);
				exit_wa(buf);
			}
		}
		// now check if paths are node-disjoint
		for (int i=0; i<m; ++i) {
			int cpos = e[i];
			int cpos2 = a[i];
			int fac = n;
			// calculate the nodes in each layer which are traversed by the path
			for (int j=k-1; j>=0; --j) {
				if (num[i]&(1<<j)) {
					if (cpos % fac < fac/2)
						cpos += fac/2;
					if (cpos2 % fac < fac/2)
						cpos2 += fac/2;
				}
				else {
					if (cpos % fac >= fac/2)
						cpos -= fac/2;
					if (cpos2 % fac >= fac/2)
						cpos2 -= fac/2;
				}
				set_visit(cpos, j);
				set_visit(cpos, j+k);
				fac /= 2;
			}
			if (cpos != cpos2 || cpos != num[i]) {
				fprintf(stderr, "fatal error: switch number leads to invalid path, there must be a bug in the judge\n");
				exit(1);
			}
		}
	}
	char c = fgetc(out);
	if (c != EOF) {
		char buf[100];
		sprintf(buf, "EOF expected, got %c\n", c);
		exit_wa(buf);
	}
	fprintf(stderr,"Accepted\n");
	return ACC;
}
