Untitled

package day10_1206;

import java.util.Scanner;

public class map_coloring {
	
	static int[][] map;
	static int[] color;
	static boolean flag;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int testcase = sc.nextInt();
		for(int tc = 1; tc <= testcase; tc++){
			int countries = sc.nextInt(), borders = sc.nextInt();
			map = new int[countries + 1][countries + 1]; color = new int[countries + 1];
			
			int x, y;
			for(int i = 0; i < borders; i++){
				x = sc.nextInt(); y = sc.nextInt();
				map[x][y] = 1; map[y][x] = 1;
			}
			
			for(int i = 1; i <= countries; i++){
				color[i] = -1;
			}
			color[1] = 0;
			
			MyQueue cntr = new MyQueue(countries * countries);
			cntr.enqueue(1);
			int buf;
			flag = true;
			while(!cntr.isEmpty()){
				buf = cntr.dequeue();
				for(int i = 1; i <= countries; i++){
					if(map[buf][i] == 1){
						if(color[i] == -1){
							color[i] = 1 - color[buf];
							cntr.enqueue(i);
							
						}
						else if(color[i] != 1 - color[buf]){
							flag = false;
							break;
						}
					}
				}
				if(!flag) break;
			}
			System.out.print("#" + tc + " ");
			if(flag){
				for(int i = 1; i <= countries; i++){
					System.out.print(color[i]);
				}
			}
			else System.out.print(-1);
			System.out.println();
		}
	}

}