#include <bits/stdc++.h>
using namespace std;

namespace std {

	template<class Fun>
	class y_combinator_result {
		Fun fun_;
	public:
		template<class T>
		explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
	
		template<class ...Args>
		decltype(auto) operator()(Args &&...args) {
			return fun_(std::ref(*this), std::forward<Args>(args)...);
		}
	};
	
	template<class Fun>
	decltype(auto) y_combinator(Fun &&fun) {
		return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
	}
	
} // namespace std
	
void solve(){
	int N, M;
	cin >> N >> M;
	vector<vector<int>> adj(N);
	for(int i = 0; i < M; i++){
		int u, v;
		cin >> u >> v;
		u--; v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	if(N % 2 == 1){
		cout << -1 << '\n';
		return;
	}
	vector<int> vis(N, 0);
	vector<int> par(N);
	vector<int> depth(N);
	vector<vector<int> > ch(N);
	y_combinator(
		[&](auto self, int v) -> void {
			vis[v] = 1;
			for(int w : adj[v]){
				if(vis[w]) continue;
				par[w] = v;
				depth[w] = depth[v] + 1;
				ch[v].push_back(w);
				self(w);
			}
		}
	)(0);
	vector<set<int> > down(N), up(N);
	for(int v = 0; v < N; v++){
		for(int w : adj[v]){
			if(depth[w] > depth[v]){
				down[v].insert(w);
			} else {
				up[v].insert(w);
			}
		}
	}
	vector<int> color(N, -1);
	vector<int> match(N, -1);
	int ncc = 0;
	y_combinator(
		[&](auto self, int v) -> void {
			for(int w : ch[v]){
				self(w);
			}
			if(down[v].empty()) return;
			vector<int> leaf, nonleaf;
			for(int w : down[v]){
				if(up[w].size() == 1){
					leaf.push_back(w);
				} else {
					nonleaf.push_back(w);
				}
			}
			vector<int> kill;
			if(nonleaf.empty() && leaf.size() % 2 == 0){
				for(int w : down[v]){
					match[w] = v;
				}
				kill = vector<int>(down[v].begin(), down[v].end());
			} else {
				kill = leaf;
				kill.insert(kill.end(), nonleaf.begin(), nonleaf.end());
				if(kill.size() % 2 == 0) kill.pop_back();
				kill.push_back(v);
				for(int w : kill) color[w] = ncc;
				ncc++;
			}
			for(int x : kill){
				for(int y : up[x]){
					down[y].erase(x);
				}
				up[x] = {};
				for(int y : down[x]){
					up[y].erase(x);
				}
				down[x] = {};
			}
		}
	)(0);
	y_combinator(
		[&](auto self, int v) -> void {
			if(match[v] >= 0){
				color[v] = color[match[v]];
			}
			for(int w : ch[v]) self(w);
		}
	);
	for(int i = 0; i < N; i++){
		cout << (color[i]+1) << " \n"[i+1 == N];
	}
}

int main(){
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	int T;
	cin >> T;
	while(T--) solve();
}
