//413 SGU Berland Division
//Date: 1391/7/29
//Author: ShervinKH145

#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
using namespace std;

struct node
{
	list<short> contains;
	vector<short> childs;
	bool up;
	short parent;
};

const short MAX = 101;
bool adj[MAX][MAX];
node graph[MAX];

bool mark[MAX];
short countryid[MAX];
short t, n, m;
short deepLeaf, deepLeafHeight, rem, counter;

void DFS(short cur, short depth);

int main()
{
	ios_base::sync_with_stdio(false);

	cin >> t;

	for (int i = 0; i < t; i++)
	{
		cin >> n >> m;
		
		for (int j = 0; j < n; j++)
		{
			graph[j].contains.clear();
			graph[j].contains.push_back(j);
		}

		for (int j = 0; j < n; j++)
			for (int k = 0; k < n; k++)
				adj[j][k] = false;

		short a, b;
		for (int j = 0; j < m; j++)
		{
			cin >> a >> b;
			a--;
			b--;
			adj[a][b] = adj[b][a] = true;
		}

		counter = 0;
		rem = n;

		while (rem)
		{
			fill(mark, mark+n, 0);

			deepLeaf = -1;
			deepLeafHeight = -1;

			graph[0].parent = -1;

			DFS(0, 0);

			short numLeaf = 0;
			short fbi = -1;
			for (vector<short>::iterator it = graph[deepLeaf].childs.begin(); it != graph[deepLeaf].childs.end(); it++)
				if (!graph[*it].up)
					numLeaf++;
				else
					fbi = *it;

			if (numLeaf & 1)
			{
				for (vector<short>::iterator it = graph[deepLeaf].childs.begin(); it != graph[deepLeaf].childs.end(); it++)
					if (!graph[*it].up)
						graph[deepLeaf].contains.splice(graph[deepLeaf].contains.end(), graph[*it].contains);

				for (list<short>::iterator it = graph[deepLeaf].contains.begin(); it != graph[deepLeaf].contains.end(); it++)
					countryid[*it] = counter;

				counter++;
				for (int j = 0; j < n; j++)
					adj[j][deepLeaf] = false;

				rem -= numLeaf+1;
			}
			else
			{
				for (vector<short>::iterator it = graph[deepLeaf].childs.begin(); it != graph[deepLeaf].childs.end(); it++)
					if (!graph[*it].up)
					{
						adj[deepLeaf][*it] = adj[*it][deepLeaf] = false;
						graph[deepLeaf].contains.splice(graph[deepLeaf].contains.end(), graph[*it].contains);
					}

				if (fbi != -1)
				{
					graph[deepLeaf].contains.splice(graph[deepLeaf].contains.end(), graph[fbi].contains);
					for (list<short>::iterator it = graph[deepLeaf].contains.begin(); it != graph[deepLeaf].contains.end(); it++)
						countryid[*it] = counter;

					counter++;
					for (int j = 0; j < n; j++)
						adj[j][fbi] = adj[j][deepLeaf] = false;

					rem -= numLeaf+2;
				}
			}
		}

		for (int i = 0; i < n; i++)
			cout << countryid[i]+1 << ' ';
		cout << endl;
	}

	return 0;
}

void DFS(short cur, short depth)
{
	mark[cur] = true;

	bool leaf = true;
	graph[cur].up = false;
	graph[cur].childs.clear();

	for (int i = 0; i < n; i++)
		if (adj[cur][i])
		{
			if (!mark[i])
			{
				graph[cur].childs.push_back(i);
				graph[i].parent = cur;
				leaf = false;
				DFS(i, depth+1);
			}
			else if (i != graph[cur].parent)
				graph[cur].up = true;
		}

	if (leaf && depth-1 > deepLeafHeight)
	{
		deepLeafHeight = depth-1;
		deepLeaf = graph[cur].parent;
	}
}