#include <iostream>
#include <fstream>
using namespace std;
int n, e;
int arr[1001][1001];
int visited[1001];
int color[1001];
int ans[1001];
int c;
typedef struct Point {
int x, y;
};
Point E[10001];
void DFS(int i) {
for (int j = 1; j <= n; j++) {
if (arr[i][j] == 1 && visited[j] == 0) {
visited[j] = 1;
color[j] = 1 - color[i];
ans[c++] = j;
DFS(j);
}
}
}
void reset() {
for (int i = 1; i <= n; i++) {
visited[i] = 0;
color[i] = 0;
ans[i] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
arr[i][j] = 0;
}
}
}
int main() {
ifstream input("input.txt");
fstream output;
output.open("output.txt");
int t;
input >> t;
for (int tc = 1; tc <= t; tc++) {
input >> n >> e;
reset();
int p, q;
for (int i = 1; i <= e; i++) {
input >> p >> q;
E[i].x = p;
E[i].y = q;
arr[p][q] = 1;
arr[q][p] = 1;
}
visited[1] = 1;
color[1] = 0;
ans[1] = 1;
c = 2;
DFS(1);
bool flag = true;
for (int i = 1; i <= e; i++) {
if (color[E[i].x] == color[E[i].y]) {
flag = false;
break;
}
}
output << "#" << tc << " ";
//output << n << " " << c - 1 << endl;
if (!flag)
output << "-1";
else {
for (int i = 1; i <= n; i++)
output << color[i];
}
output << endl;
}
}