Untitled

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;
                        }
                    }
                }
            }
        }
    }
}