mapcoloring

#include <iostream>
#define MAX_Q 40000
using namespace std;
int soquocgia, sobiengioi;
int matrix[1005][1005];
int visited[1005];
int save_mau[1005];
class Queue
{
private:
	int front, rear;
	int arr[MAX_Q];
public:
	Queue() {
		front = rear = 0;
	}

	void push(int x) {
		arr[rear++] = x;
	}
	int pop() {
		return arr[front++];
	}
	bool empty() {
		return front == rear;
	}
};

void bfs(int dinh) {
	Queue q;
	q.push(dinh);
	visited[dinh] = 1;
	while (!q.empty())
	{
		int tmp = q.pop();
		for (int i = 1; i <= soquocgia; i++)
		{
			if (matrix[tmp][i] ==  1 && visited[i] == 0 && save_mau[tmp] != save_mau[i])
			{
				if (save_mau[tmp] == 0)
				{
					save_mau[i] = 1;
				}
				else if (save_mau[tmp] == 1) {
					save_mau[i] = 0;
				}
				visited[i] = 1;
				q.push(i);
			}
			else if (matrix[tmp][i] == 1 && visited[i] == 0 && save_mau[tmp] == save_mau[i])
			{
				return;
			}
		}
	}
}
int check() {
	for (int i = 1; i <= soquocgia; i++)
	{
		if (visited[i] == 0)
		{
			return 1;
		}
	}
	return 0;
}
int main()
{
	int T;
	cin >> T;
	for (int yc = 0; yc < T; yc++)
	{
		cin >> soquocgia >> sobiengioi;
		for (int i = 0; i < 1005; i++)
		{
			for (int j = 0; j < 1005; j++)
			{
				matrix[i][j] = matrix[j][i] = 0;
			}
		}
		for (int i = 1; i <= sobiengioi; i++)
		{
			int x, y;
			cin >> x >> y;
			matrix[x][y] = matrix[y][x] = 1;
		}
		for (int i = 1; i <= soquocgia; i++)
		{
			save_mau[i] = -1;
			visited[i] = 0;
		}
		save_mau[1] = 0;
		bfs(1);
		if (check() == 1)
		{
			cout << -1 << "";
		}
		else
		{
			for (int i = 1; i <= soquocgia; i++)
			{
				cout << save_mau[i];
			}
		}
		cout << endl;

	}
	return 0;
}