/* --------Official Solution ---------
	@author : triveni (Triveni Mahatha)
	
	Note that the problem can be reduced to 2SAT.
	We can then use Tarjan's algorithm to solve. 
	Main component of Tarjan's algorithm is to 
	find strongly connected components. In this
	solution, I am using Kosaraju's algorithm for
	that. Time compleixty is linear O(n + m).
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> VI;

int which_comp[200100];// which connected component does node i belong
int f_ans[200100]; 	// f_ans[i] : what is the truth assignment for component i
bool vis[200100];
int who[200100]; 		// who[i] : what is the node visited at time i

void dfs(int u, int& cur_t, const vector<VI> & graph){
	vis[u] = 1;
	for(int c : graph[u]) if(!vis[c]) {
		dfs(c, cur_t, graph);
	}
	who[cur_t++] = u;
}

void dfs2(int u, int comp_num, const vector<VI> & graph){
	which_comp[u] = comp_num;
	for(int c : graph[u]) if(which_comp[c] == -1){
		dfs2(c, comp_num, graph);
	}
	return ;
}

void dfs3(int u, const vector<VI> & graph, bool truthValue) {
	vis[u] = true;
	int c = which_comp[u ^ 1];
	assert(truthValue != f_ans[c]);
	f_ans[c] = !truthValue;

	for (int c : graph[u]) if (!vis[c]) {
		dfs3(c, graph, truthValue);
	}
}

bool kosarajuSCC(int n, const vector<VI>& graph, const vector<VI>& revGraph, vector<bool> & ans) {
	n += n % 2;
	int curTime = 0;

	for (int i = 0; i < n; ++i) {
		vis[i] = 0;
		who[i] = -1;
		f_ans[i] = -1;
		which_comp[i] = -1;
	}
	for(int i = 0; i < n; ++i) if(!vis[i]) {
		dfs(i, curTime, revGraph);
	}
	for (int i = n-1; i >= 0; --i) if(which_comp[who[i]] == -1){
		dfs2(who[i], who[i], graph);
	}
	for (int i = 0; i < n; i += 2) {
		vis[i] = vis[i + 1] = 0;
		if (which_comp[i] == which_comp[i ^ 1]) return false;
	}
	for (int i = n-1; i >= 0; --i) if (!vis[who[i]]) {
		int u = who[i];
		dfs3(u, graph, f_ans[which_comp[u]] == -1 ? true : f_ans[which_comp[u]]);
	}
	// needs for verification
	for (int i = 0; i < ans.size(); ++i) {
		ans[i] = f_ans[which_comp[i]];
	}
	return true;
}

void verify(vector<pair<int, int> > & edges, vector<bool> & truthAssignment){
	for (pair<int, int> p : edges) {
		assert(truthAssignment[p.first] || truthAssignment[p.second]);
	}
	for (int i = 0; i < truthAssignment.size(); ++i){
		if((i ^ 1) < truthAssignment.size()) 
			assert(truthAssignment[i] ^ truthAssignment[i^1]);
	}
	return ;
}

int main() {
	int T, sumN = 0, sumM = 0;
	scanf("%d", &T);
	assert(1 <= T && T <= 100000);

	while(T--) {
		int n, m;
		scanf("%d %d", &n, &m);
		assert(1 <= n && n <= 300000);
		assert(0 <= m && m <= 300000);
		sumM += m;
		sumN += n;
		assert(1 <= sumN && sumN <= 1000000);
		assert(0 <= sumM && sumM <= 1000000);

		vector<vector<int> > impGraph(n+1);
		vector<vector<int> > revGraph(n+1);
		vector<pair<int, int> > edges;

		unordered_set<ll> uniqueEdges;
		for (int i = 0; i < m; ++i) {
			int u, v;
			scanf("%d %d", &u, &v);
			assert(1 <= u && u <= n);
			assert(1 <= v && v <= n);
			assert(u != v);
			--u, --v;
			ll edgeHash = max<ll>(u, v) * n + min<ll>(u, v);
			assert(uniqueEdges.find(edgeHash) == uniqueEdges.end());
			uniqueEdges.insert(edgeHash);

			edges.push_back(make_pair(u, v));
			impGraph[u ^ 1].push_back(v);
			impGraph[v ^ 1].push_back(u);
			revGraph[v].push_back(u ^ 1);
			revGraph[u].push_back(v ^ 1);
		}
		vector<bool> truthAssignment(n);
		bool possible = kosarajuSCC(n, impGraph, revGraph, truthAssignment);
		if (!possible) {
			puts("impossible");
			continue;
		}
		puts("possible");
		for (int i = 0; i < n; ++i) putchar(truthAssignment[i] + '0');
		putchar(10);
		verify(edges, truthAssignment);
	}
	return 0;
}