#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void read(int &x) {
	char c;
	while (!isdigit(c = getchar()));
	x = c ^ 48;
	while (isdigit(c = getchar())) x = x * 10 + (c ^ 48);
}
vector<int> e[100005], eO[100005], eR[100005], eN[100005];
int T, n, m;
int rt, deg[100005], fa[100005];
int F(int u) { return fa[u] == u ? u : fa[u] = F(fa[u]); }
void Merge(int x, int y) {
	if (eO[x].size() < eO[y].size() + eR[y].size()) {
		for (int v : eO[x]) {
			if (F(v) == y) deg[y]--;
			else if (F(v) != x) eO[y].push_back(v);
		}
	}
	else {
		for (int v : eR[y]) {
			if (F(v) == x) deg[y]--;
		}
		for (int v : eO[y]) {
			if (F(v) != x) eO[x].push_back(v);
		}
		eO[x].swap(eO[y]);
	}
	fa[x] = y;
}
int FindR() {
	for (int i = 1; i <= n; i++) {
		eO[i] = e[i], fa[i] = i;
		for (int v : e[i]) deg[v]++;
	}
	queue<int> q;
	for (int i = 1; i <= n; i++) if (deg[i] <= 1) q.push(i), deg[i] = 0;
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int v : eR[u]) {
			if (F(v) == u) continue;
			Merge(u, F(v));
			if (deg[F(v)] == 1) q.push(F(v)), deg[F(v)] = 0;
			break;
		}
	}
	int c = 0, p = 0;
	for (int i = 1; i <= n; i++) {
		if (F(i) == i) {
			c++, p = i;
		}
	}
	return c > 1 ? 0 : p;
}
int dfn[100005], low[100005], cti, bel[100005], cnt, st[100005], top;
bool vis[100005], ind[100005];
void Tarjan(int u) {
	vis[u] = true; st[++top] = u;
	dfn[u] = low[u] = ++cti;
	for (int v : e[u]) {
		if (!dfn[v]) {
			Tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if (vis[v]) low[u] = min(low[u], dfn[v]);
	}
	if (dfn[u] == low[u]) {
		cnt++;
		while (vis[u]) {
			int x = st[top--];
			vis[x] = false; bel[x] = cnt;
		}
	}
}
int ans[100005], dep[100005], prt[100005];
struct Dat {
	ll x, y;
	Dat &operator+=(const Dat &b) {
		x += b.x, y += b.y;
		return *this;
	}
	Dat &operator-=(const Dat &b) {
		x -= b.x, y -= b.y;
		return *this;
	}
};
Dat f[100005];
int g[100005];
void DFS1(int u) {
	for (int v : e[u]) {
		if (v != rt && !prt[v]) {
			prt[v] = u, dep[v] = dep[u] + 1, DFS1(v);
			f[u] += f[v];
		}
		else {
			f[u] += { 1, v }, f[v] -= { 1, v };
		}
	}
}
int sum[100005];
void DFS2(int u) {
	if (bel[u] != bel[rt]) ans[u] = 3;
	else if (u != rt && f[u].x == 1) ans[u] = ans[f[u].y];
	sum[u] += ans[u];
	for (int v : e[u]) {
		if (u == prt[v]) {
			sum[v] = sum[u];
			DFS2(v);
			g[u] += g[v];
		}
		else if (ans[v] && sum[u] > sum[v]) {
			g[u]++, g[v]--;
		}
		else eN[v].push_back(u);
	}
	if (!ans[u]) {
		if (g[u] == 1) ans[u] = 2;
		else if (g[u] > 1) ans[u] = 3;
	}
}
void DFS3(int u) {
	if (bel[u] != bel[rt]) return;
	if (ans[u] == 1 || ans[u] == 2) {
		for (int v : eN[u]) {
			for (int x = v; !vis[x]; vis[x] = true, x = prt[x]) {
				if (!ans[x]) ans[x] = 2;
			}
		}
	}
	if (!ans[u]) ans[u] = 3;
	for (int v : e[u]) if (prt[v] == u) DFS3(v);
}
int main() {
	read(T), read(T);
	while (T--) {
		read(n), read(m);
		for (int i = 1, u, v; i <= m; i++) {
			read(u), read(v);
			e[u].push_back(v), eR[v].push_back(u);
		}
		for (int i = 1; i <= n; i++) if (!dfn[i]) Tarjan(i);
		for (int u = 1; u <= n; u++) {
			for (int v : e[u]) {
				if (bel[u] != bel[v]) ind[bel[v]] = true;
			}
		}
		int nCnt = 0;
		for (int u = 1; u <= cnt; u++) {
			if (!ind[u]) nCnt++;
		}
		rt = FindR();
		if (nCnt >= 2) {
			for (int i = 1; i <= n; i++) putchar('3');
			putchar('\n');
		}
		else if (!rt) {
			for (int i = 1; i <= n; i++) putchar("23"[bel[i] != cnt]);
			putchar('\n');
		}
		else {
			ans[rt] = 1;
			DFS1(rt), DFS2(rt), DFS3(rt);
			for (int i = 1; i <= n; i++) putchar('0' + ans[i]);
			putchar('\n');
		}
		for (int i = 1; i <= n; i++) {
			e[i].clear(), eR[i].clear(), eN[i].clear();
			deg[i] = dfn[i] = bel[i] = ind[i] = ans[i] = dep[i] = prt[i] = sum[i] = vis[i] = g[i] = 0;
			f[i] = { 0, 0 };
		}
		rt = cnt = 0;
	}
	return 0;
}