#include<iostream>
using namespace std;
int T, d, n;
int arr[1005][1005], visit[1005];
int rs, flag;
void nhap() {
cin >> d >> n;
for(int i = 0; i < d; i ++) {
for(int j = 0; j < d; j ++) {
arr[i][j] = 0;
}
}
for(int i = 0; i < n; i ++) {
int a, b;
cin >> a >> b;
a --; b --;
arr[a][b] = 1;
arr[b][a] = 1;
}
}
void reset() {
for(int i = 0; i < d; i ++) {
visit[i] = -1;
}
}
void dequy(int gg, int t, int m = 1) {
for(int i = 0; i < d; i ++) {
if(arr[t][i] && visit[i] == -1) {
visit[i] = m;
for(int j = 0; j < d; j ++) {
if(arr[i][j] && visit[j] == visit[i]) {
flag = 1;
return;
}
}
int k = (m+1)%2;
dequy(gg+1,i,k);
}
}
}
int main() {
freopen("input.txt", "r", stdin);
ios::sync_with_stdio(false);
cin >> T;
for(int t = 1; t <= T; t ++) {
rs = 0;
nhap();
reset();
cout << "#" << t << " ";
flag = 0;
for(int i = 0; i < d; i++) {
if(visit[i] == -1) {
visit[i] = 0;
dequy(0,0);
}
if(flag == 1) break;
}
if(flag == 0) for(int i = 0; i < d; i ++) cout << visit[i];
else cout << -1;
cout << endl;
}
return 0;
}