package MapColoring;
import java.io.FileInputStream;
import java.io.PrintStream;
import java.util.Scanner;
/**
* Solution
*/
public class Solution {
static int N,E,f,r;
static int[] U,V,Q,visited;
static boolean check;
public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream("input.txt"));
System.setOut(new PrintStream("output.txt"));
Scanner sc = new Scanner(System.in);
int tc = sc.nextInt();
for(int t=1;t<=tc;t++){
N = sc.nextInt();
E = sc.nextInt();
U = new int[E];
V = new int[E];
Q = new int[N];
visited = new int[N+1];
for(int i=0;i<E;i++){
U[i] = sc.nextInt();
V[i] = sc.nextInt();
}
check = true;
for(int i=1;i<=N;i++){
if(visited[i]==0){
BFS(i);
if(!check) break;
}
}
System.out.print("#"+t+" ");
if(!check){
System.out.print(-1);
}
else{
for(int i=1;i<=N;i++){
System.out.print(1-visited[i]%2);
}
}
System.out.println();
}
}
static void BFS(int x){
f = 0; r = 0;
Q[r++] = x;
visited[x] = 1;
while(f<r){
int p = Q[f++];
for(int i = 0;i<E;i++){
if(U[i]==p){
if(visited[V[i]]==0){
Q[r++] = V[i];
visited[V[i]] = visited[p]+1;
}
else {
if(visited[V[i]]%2==visited[p]%2){
check = false;
return;
}
}
}
else if(V[i]==p){
if(visited[U[i]]==0){
Q[r++] = U[i];
visited[U[i]] = visited[p]+1;
}
else {
if(visited[U[i]]%2==visited[p]%2){
check = false;
return;
}
}
}
}
}
}
}