#include <bits/stdc++.h>

using namespace std;

const int MaxN = 4e5 + 10;
const long long INF = 1e18;

vector < int > g[MaxN], gt[MaxN], top;
int color[MaxN], used[MaxN], n, m;
int repr[MaxN], bad[MaxN], res[MaxN];

int conj(int v) {
    return v ^ 1;
}

void dfs(vector < int > g[], int v, int f = -1) {
    used[v] = 1;
    for (size_t i = 0; i < g[v].size(); ++i) {
        int to = g[v][i];
        if (!used[to])
            dfs(g, to, f);
    }
    if (f == -1) {
        top.push_back(v);
    } else {
        color[v] = f;
        repr[f] = v;
    }
}

void add(int u, int v) {
    g[u].push_back(v);
    gt[v].push_back(u);
    g[conj(v)].push_back(conj(u));
    gt[conj(u)].push_back(conj(v));
}

void addor(int u, int v, int c) {
    if (c == 1) {
        add(conj(u), v);
    } else {
        add(u, conj(u));
        add(v, conj(v));
    }
}

void addxor(int u, int v, int c) {
    if(c == 0) {
        add(u, v);
        add(v, u);
    } else {
        add(u, conj(v));
        add(conj(u), v);
    }
}

void addand(int u, int v, int c) {
    if (c == 0) {
        add(u, conj(v));
    } else {
        add(conj(u), u);
        add(conj(v), v);
    }
}

int main() {
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
    int t;
    scanf("%d", &t);
    assert (1 <= t && t <= 100000);
    int en = 0, em = 0;
    while (t --> 0) {
		scanf("%d%d", &n, &m);
		assert (1 <= n && n <= 200000);
		assert (0 <= m && m <= 200000);
		for (int i = 0; i <= 2 * n; ++i) {
			g[i].clear();
			gt[i].clear();
			color[i] = used[i] = 0;
			bad[i] = repr[i] = 0;
		}
		top.clear();
		en += n;
		em += m;
		for (int i = 0; i < n / 2; ++i) {
			int u = 2 * i, v = 2 * i + 1;
			addxor(2 * u, 2 * v, 1);
		}
		vector < pair < int, int > > edges;
		for (int i = 0; i < m; ++i) {
			int x, y;
			scanf("%d%d", &x, &y);
			edges.push_back(make_pair(x - 1, y - 1));
			assert (1 <= x && x <= n);
			assert (1 <= y && y <= n);
			assert (x != y);
			x += x - 2;
			y += y - 2;
			addor(x, y, 1);
		}
		fill(used, used + 2 * n, 0);
		for (int i = 0; i < 2 * n; ++i) {
			if (!used[i]) {
				dfs(g, i);
			}
		}
		reverse(top.begin(), top.end());
		fill(used, used + 2 * n, 0);
		int cnt = 0;
		for (size_t i = 0; i < top.size(); ++i) {
			int v = top[i];
			if (!used[v]) {
				dfs(gt, v, ++cnt);
			}
		}
		bool can = true;
		for (int i = 0; i < 2 * n; ++i) {
			if(color[i] == color[conj(i)]) {
				can = false;
			}
		}
		if (!can) {
			printf("impossible\n");
			continue;
		}
		printf("possible\n");
		for (int i = 0; i < 2 * n; i += 2) {
			printf("%d", color[i] > color[conj(i)] ? 1 : 0);
		}
		printf("\n");
    }
    assert (1 <= en && en <= 1000000);
    assert (1 <= em && em <= 1000000);
    return 0;
}