You are given a directed graph $G$ which can contain loops (edges from a vertex to itself). Multi-edges are absent in $G$ which means that for all ordered pairs $(u, v)$ exists at most one edge from $u$ to $v$. Vertices are numbered from $1$ to $n$.

A path from $u$ to $v$ is a sequence of edges such that:

vertex $u$ is the start of the first edge in the path;

vertex $v$ is the end of the last edge in the path;

for all pairs of adjacent edges next edge starts at the vertex that the previous edge ends on.

We will assume that the empty sequence of edges is a path from $u$ to $u$.

For each vertex $v$ output one of four values:

$0$, if there are no paths from $1$ to $v$;

$1$, if there is only one path from $1$ to $v$;

$2$, if there is more than one path from $1$ to $v$ and the number of paths is finite;

$-1$, if the number of paths from $1$ to $v$ is infinite.

Let's look at the example shown in the figure.

Then:

the answer for vertex $1$ is $1$: there is only one path from $1$ to $1$ (path with length $0$);

the answer for vertex $2$ is $0$: there are no paths from $1$ to $2$;

the answer for vertex $3$ is $1$: there is only one path from $1$ to $3$ (it is the edge $(1, 3)$);

the answer for vertex $4$ is $2$: there are more than one paths from $1$ to $4$ and the number of paths are finite (two paths: $[(1, 3), (3, 4)]$ and $[(1, 4)]$);

the answer for vertex $5$ is $-1$: the number of paths from $1$ to $5$ is infinite (the loop can be used in a path many times);

the answer for vertex $6$ is $-1$: the number of paths from $1$ to $6$ is infinite (the loop can be used in a path many times).


-----Input-----

The first contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the input. Then $t$ test cases follow. Before each test case, there is an empty line.

The first line of the test case contains two integers $n$ and $m$ ($1 \le n \le 4 \cdot 10^5, 0 \le m \le 4 \cdot 10^5$) — numbers of vertices and edges in graph respectively. The next $m$ lines contain edges descriptions. Each line contains two integers $a_i$, $b_i$ ($1 \le a_i, b_i \le n$) — the start and the end of the $i$-th edge. The vertices of the graph are numbered from $1$ to $n$. The given graph can contain loops (it is possible that $a_i = b_i$), but cannot contain multi-edges (it is not possible that $a_i = a_j$ and $b_i = b_j$ for $i \ne j$).

The sum of $n$ over all test cases does not exceed $4 \cdot 10^5$. Similarly, the sum of $m$ over all test cases does not exceed $4 \cdot 10^5$.


-----Output-----

Output $t$ lines. The $i$-th line should contain an answer for the $i$-th test case: a sequence of $n$ integers from $-1$ to $2$.


-----Examples-----

Input
5

6 7
1 4
1 3
3 4
4 5
2 1
5 5
5 6

1 0

3 3
1 2
2 3
3 1

5 0

4 4
1 2
2 3
1 4
4 3
Output
1 0 1 2 -1 -1 
1 
-1 -1 -1 
1 0 0 0 0 
1 1 2 1


-----Note-----

None

Source: codeforces | Difficulty: HARD
Tags: Tree algorithms

Graph algorithms

Graph traversal

Dynamic programming


Solutions:
from collections import deque

def cyc(n, path):
	(visi, poi) = ([2] + [0] * (n - 1), [0] * n)
	inf = []
	multi = []
	st = [0]
	while len(st):
		(x, y) = (st[-1], poi[st[-1]])
		if y == len(path[x]):
			visi[st.pop()] = 1
		else:
			z = path[x][y]
			if visi[z] == 2:
				inf.append(z)
				poi[x] += 1
				continue
			if visi[z] == 1:
				multi.append(z)
				poi[x] += 1
				continue
			st.append(z)
			poi[x] += 1
			visi[z] = 2
	ans = [1] * n
	for i in range(n):
		if not visi[i]:
			ans[i] = 0
	curr = deque(multi)
	vv = [0] * n
	for i in multi:
		vv[i] = 1
	while len(curr):
		x = curr.popleft()
		ans[x] = 2
		for y in path[x]:
			if not vv[y]:
				vv[y] = 1
				curr.append(y)
	curr = deque(inf)
	vv = [0] * n
	for i in inf:
		vv[i] = 1
	while len(curr):
		x = curr.popleft()
		ans[x] = -1
		for y in path[x]:
			if not vv[y]:
				vv[y] = 1
				curr.append(y)
	return ans
for _ in range(int(input())):
	input()
	(n, m) = map(int, input().split())
	path = [[] for _ in range(n)]
	for _ in range(m):
		(aa, bb) = map(int, input().split())
		path[aa - 1].append(bb - 1)
	print(*cyc(n, path))


import sys
sys.setrecursionlimit(600000)

def dfs_1(v):
	q = [v, 0]
	while len(q) != 0:
		i = q.pop()
		v = q.pop()
		if i == 0:
			color[v] = 1
		if i == len(g[v]):
			color[v] = 2
			continue
		q.append(v)
		q.append(i + 1)
		w = g[v][i]
		if color[w] == 0:
			q.append(w)
			q.append(0)
		elif color[w] == 1:
			in_cycles.append(w)
		elif color[w] == 2:
			more_than_one.append(w)

def dfs_2(v):
	q = [v, 0]
	while len(q) != 0:
		i = q.pop()
		v = q.pop()
		if i == 0:
			color_tmp[v] = 1
		if i == len(g[v]):
			color_tmp[v] = 2
			continue
		q.append(v)
		q.append(i + 1)
		w = g[v][i]
		if color_tmp[w] == 0:
			q.append(w)
			q.append(0)

def fill_not_accessible(color, answer):
	for (i, c) in enumerate(color):
		if c == 0:
			answer[i] = 0

def fill_more_than_one(color, answer):
	for (i, c) in enumerate(color):
		if c == 2:
			answer[i] = 2

def fill_inf(color, answer):
	for (i, c) in enumerate(color):
		if c == 2:
			answer[i] = -1
t = int(input())
for _ in range(t):
	input()
	(n, m) = map(int, input().split())
	color = [0 for _ in range(n + 1)]
	g = {i: [] for i in range(n + 1)}
	in_cycles = []
	more_than_one = []
	answer = [1 for _ in range(n + 1)]
	for _ in range(m):
		(a, b) = map(int, input().split())
		g[a].append(b)
	dfs_1(1)
	fill_not_accessible(color, answer)
	color_tmp = [0 for _ in range(n + 1)]
	for x in more_than_one:
		if color_tmp[x] == 0:
			dfs_2(x)
	fill_more_than_one(color_tmp, answer)
	color_tmp = [0 for _ in range(n + 1)]
	for x in in_cycles:
		if color_tmp[x] == 0:
			dfs_2(x)
	fill_inf(color_tmp, answer)
	print(' '.join(map(str, answer[1:])))


import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def find_SCC(graph):
	(SCC, S, P) = ([], [], [])
	depth = [0] * len(graph)
	stack = list(range(len(graph)))
	while stack:
		node = stack.pop()
		if node < 0:
			d = depth[~node] - 1
			if P[-1] > d:
				SCC.append(S[d:])
				del S[d:], P[-1]
				for node in SCC[-1]:
					depth[node] = -1
		elif depth[node] > 0:
			while P[-1] > depth[node]:
				P.pop()
		elif depth[node] == 0:
			S.append(node)
			P.append(len(S))
			depth[node] = len(S)
			stack.append(~node)
			stack += graph[node]
	return SCC[::-1]
for _ in range(int(input())):
	input()
	(n, m) = [int(i) for i in input().split()]
	g = [[] for i in range(n)]
	scc = []
	for i in range(m):
		(u, v) = [int(i) - 1 for i in input().split()]
		g[u].append(v)
		if u == v:
			scc.append([u])
	s1 = find_SCC(g)
	for i in s1:
		if len(i) > 1:
			scc.append(i[:])
	infinite = [0] * n
	for i in scc:
		for j in i:
			infinite[j] = -1
	vis = [0] * n
	stack = [0]
	vis[0] = 1
	if infinite[0]:
		vis[0] = -1
		stack1 = [0]
		while len(stack1):
			curr1 = stack1.pop()
			for i1 in g[curr1]:
				if vis[i1] != -1:
					vis[i1] = -1
					stack1.append(i1)
	while stack:
		curr = stack.pop()
		for i in g[curr]:
			if not vis[i]:
				stack.append(i)
				vis[i] = 1
				if infinite[i]:
					vis[i] = -1
					stack1 = [i]
					while len(stack1):
						curr1 = stack1.pop()
						for i1 in g[curr1]:
							if vis[i1] != -1:
								vis[i1] = -1
								stack1.append(i1)
			elif vis[i] == 1:
				vis[i] += 1
				stack.append(i)
	print(*vis)


import os, sys
from io import BytesIO, IOBase
from collections import deque

def cyc(n, path):
	(visi, poi) = ([2] + [0] * (n - 1), [0] * n)
	inf = []
	multi = []
	st = [0]
	while len(st):
		(x, y) = (st[-1], poi[st[-1]])
		if y == len(path[x]):
			visi[st.pop()] = 1
		else:
			z = path[x][y]
			if visi[z] == 2:
				inf.append(z)
				poi[x] += 1
				continue
			if visi[z] == 1:
				multi.append(z)
				poi[x] += 1
				continue
			st.append(z)
			poi[x] += 1
			visi[z] = 2
	ans = [1] * n
	for i in range(n):
		if not visi[i]:
			ans[i] = 0
	curr = deque(multi)
	vv = [0] * n
	for i in multi:
		vv[i] = 1
	while len(curr):
		x = curr.popleft()
		ans[x] = 2
		for y in path[x]:
			if not vv[y]:
				vv[y] = 1
				curr.append(y)
	curr = deque(inf)
	vv = [0] * n
	for i in inf:
		vv[i] = 1
	while len(curr):
		x = curr.popleft()
		ans[x] = -1
		for y in path[x]:
			if not vv[y]:
				vv[y] = 1
				curr.append(y)
	return ans

def main():
	for _ in range(int(input())):
		input()
		(n, m) = map(int, input().split())
		path = [[] for _ in range(n)]
		for _ in range(m):
			(aa, bb) = map(int, input().split())
			path[aa - 1].append(bb - 1)
		print(*cyc(n, path))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def find_SCC(graph):
	(SCC, S, P) = ([], [], [])
	depth = [0] * len(graph)
	stack = list(range(len(graph)))
	while stack:
		node = stack.pop()
		if node < 0:
			d = depth[~node] - 1
			if P[-1] > d:
				SCC.append(S[d:])
				del S[d:], P[-1]
				for node in SCC[-1]:
					depth[node] = -1
		elif depth[node] > 0:
			while P[-1] > depth[node]:
				P.pop()
		elif depth[node] == 0:
			S.append(node)
			P.append(len(S))
			depth[node] = len(S)
			stack.append(~node)
			stack += graph[node]
	return SCC[::-1]
for _ in range(int(input()) if True else 1):
	empty = input()
	(n, m) = map(int, input().split())
	graph = [[] for __ in range(n + 1)]
	self = [False] * (n + 1)
	for i in range(m):
		(x, y) = map(int, input().split())
		if x == y:
			self[x] = True
		graph[x] += [y]
	visited = [False] * (n + 1)
	multiple = [False] * (n + 1)
	queue = [1]
	visited[1] = True
	while queue:
		x = queue.pop()
		for y in graph[x]:
			if not visited[y]:
				visited[y] = True
				queue += [y]
			elif not multiple[y]:
				multiple[y] = True
				queue += [y]
	infinite = [False] * (n + 1)
	for comp in find_SCC(graph):
		if len(comp) > 1 or (len(comp) == 1 and self[comp[0]]):
			if not infinite[comp[0]] and visited[comp[0]]:
				queue = comp
				for x in queue:
					infinite[x] = True
				while queue:
					x = queue.pop()
					for y in graph[x]:
						if not infinite[y]:
							infinite[y] = True
							queue += [y]
	ans = []
	for i in range(1, n + 1):
		if infinite[i] and multiple[i]:
			ans += [-1]
		elif multiple[i]:
			ans += [2]
		elif visited[i]:
			ans += [1]
		else:
			ans += [0]
	print(*ans)


import sys
input = sys.stdin.buffer.readline
for _ in range(int(input())):
	x = input()
	(n, m) = map(int, input().split())
	adj = [[] for i in range(n + 1)]
	radj = [[] for i in range(n + 1)]
	for i in range(m):
		(a, b) = map(int, input().split())
		adj[a].append(b)
		radj[b].append(a)
	toposort = []
	vis = [0] * (n + 1)
	idx = [0] * (n + 1)
	for c in range(1, n + 1):
		if not vis[c]:
			vis[c] = 1
			s = [c]
			while s:
				c = s[-1]
				if idx[c] < len(adj[c]):
					ne = adj[c][idx[c]]
					if not vis[ne]:
						vis[ne] = 1
						s.append(ne)
					idx[c] += 1
				else:
					toposort.append(c)
					s.pop()
	scc = [0] * (n + 1)
	sccs = [[]]
	while toposort:
		c = toposort.pop()
		if scc[c] == 0:
			sccs.append([])
		s = [c]
		while s:
			c = s.pop()
			if scc[c] == 0:
				scc[c] = len(sccs) - 1
				sccs[-1].append(c)
				for ne in radj[c]:
					if scc[ne] == 0:
						s.append(ne)
	compressed_adj = [[] for i in range(len(sccs))]
	compressed_radj = [[] for i in range(len(sccs))]
	cycle = [0] * len(sccs)
	for a in range(1, n + 1):
		for b in adj[a]:
			if scc[a] != scc[b]:
				compressed_adj[scc[a]].append(scc[b])
				compressed_radj[scc[b]].append(scc[a])
			else:
				cycle[scc[a]] = 1
	for i in range(1, len(sccs)):
		if not cycle[i] and len(sccs[i]) > 1:
			raise RuntimeError
	ans = [0] * (n + 1)
	for i in range(1, len(sccs)):
		if 1 in sccs[i]:
			start = i
	reachable_cycles = []
	s = [start]
	vis = [0] * (n + 1)
	idx = [0] * (n + 1)
	while s:
		c = s[-1]
		if not vis[c]:
			vis[c] = 1
			if cycle[c]:
				reachable_cycles.append(c)
			else:
				for i in sccs[c]:
					ans[i] = 1
		if idx[c] < len(compressed_adj[c]):
			ne = compressed_adj[c][idx[c]]
			if not vis[ne]:
				s.append(ne)
			idx[c] += 1
		else:
			s.pop()
	vis = [0] * (n + 1)
	idx = [0] * (n + 1)
	for c in reachable_cycles:
		s = [c]
		while s:
			c = s[-1]
			if not vis[c]:
				vis[c] = 1
				for i in sccs[c]:
					ans[i] = -1
			if idx[c] < len(compressed_adj[c]):
				ne = compressed_adj[c][idx[c]]
				if not vis[ne]:
					s.append(ne)
				idx[c] += 1
			else:
				s.pop()
	for i in range(1, n + 1):
		if cycle[scc[i]] and (not (ans[i] == -1 or ans[i] == 0)):
			raise RuntimeError
	for i in range(1, n + 1):
		if len(sccs[scc[i]]) > 1 and ans[i] == 1:
			raise RuntimeError
	for i in range(len(sccs)):
		if len(sccs[i]) > 1:
			for j in sccs[i]:
				if ans[j] == 1:
					raise RuntimeError
	paths = [0] * (n + 1)
	paths[start] = 1
	vis = [0] * (n + 1)
	idx = [0] * (n + 1)
	for c in range(1, n + 1):
		if ans[c] == 1:
			if not vis[scc[c]]:
				vis[scc[c]] = 1
				s = [scc[c]]
				while s:
					c = s[-1]
					if len(sccs[c]) > 1:
						raise RuntimeError
					if idx[c] < len(compressed_radj[c]):
						ne = compressed_radj[c][idx[c]]
						if not cycle[ne] and (not vis[ne]):
							vis[ne] = 1
							s.append(ne)
						idx[c] += 1
					else:
						for ne in compressed_adj[c]:
							if not cycle[ne]:
								paths[ne] += paths[c]
						s.pop()
	for c in range(1, n + 1):
		if ans[c] == 1:
			ans[c] = 2 if paths[scc[c]] > 1 else 1
	print(*ans[1:])


import sys
from collections import deque
input = sys.stdin.readline

def kosaraju(n, G):
	T = [[] for _ in range(n)]
	for i in range(n):
		for j in G[i]:
			T[j].append(i)
	L = []
	vis = [-1] * n
	ans = [-1] * n
	for u in range(n):
		if vis[u] != -1:
			continue
		stk = [u]
		while stk:
			w = stk[-1]
			if vis[w] == -1:
				vis[w] = 0
				for v in G[w]:
					if vis[v] != -1:
						continue
					stk.append(v)
			else:
				stk.pop()
				if vis[w] == 0:
					vis[w] = 1
					L.append(w)
	gp_symbol = -1
	while L:
		u = L.pop()
		if ans[u] == -1:
			gp_symbol += 1
			stk = [u]
			while stk:
				w = stk.pop()
				if ans[w] == -1:
					ans[w] = gp_symbol
					for v in T[w]:
						if ans[v] == -1:
							stk.append(v)
	W = [[] for _ in range(gp_symbol + 1)]
	cyc = [False] * len(W)
	sz = [0] * len(W)
	for i in range(n):
		sz[ans[i]] += 1
		for j in G[i]:
			if ans[i] != ans[j]:
				W[ans[i]].append(ans[j])
			elif i == j:
				cyc[ans[i]] = True
	return (ans, W, cyc, sz)

def solve():
	_ = input()
	(n, m) = map(int, input().split())
	G = [[] for _ in range(n)]
	for _ in range(m):
		(i, j) = map(int, input().split())
		G[i - 1].append(j - 1)
	(ref, W, cyc, sz) = kosaraju(n, G)
	A = [0] * len(W)
	q = deque([(ref[0], 0)])
	while q:
		(node, prev) = q.popleft()
		if A[node] in [2, -1] and prev != -1:
			continue
		if prev == 0:
			if ref[0] == node:
				if sz[node] > 1 or cyc[node]:
					A[node] = -1
				else:
					A[node] = 1
		elif prev == 1:
			if A[node] == 0:
				A[node] = 1
			else:
				A[node] = 2
		elif prev == 2:
			A[node] = 2
		else:
			A[node] = -1
		if sz[node] > 1 or cyc[node]:
			A[node] = -1
		for node0 in W[node]:
			q.append((node0, A[node]))
	ans = [-99] * n
	for i in range(n):
		ans[i] = A[ref[i]]
	print(*ans)
for nt in range(int(input())):
	solve()


import sys
sys.stderr = sys.stdout
from collections import deque

def solve(n, m, E):
	D = [[] for _ in range(n)]
	for (u, v) in E:
		D[u].append(v)
	P = [None] * n
	K = [0] * n
	V = [0] * n
	V[0] = 1
	A = {0}
	i = 0
	while i is not None:
		k = K[i]
		K[i] += 1
		if k < len(D[i]):
			j = D[i][k]
			if V[j] == 0:
				P[j] = i
				V[j] = 1
				A.add(j)
				i = j
			elif j in A:
				V[j] = -1
			elif V[j] == 1:
				V[j] = 2
		else:
			A.remove(i)
			i = P[i]
	Q = deque((i for i in range(n) if V[i] == -1))
	while Q:
		i = Q.pop()
		for j in D[i]:
			if V[j] != -1:
				V[j] = -1
				Q.append(j)
	Q = deque((i for i in range(n) if V[i] == 2))
	while Q:
		i = Q.pop()
		for j in D[i]:
			if V[j] == 1:
				V[j] = 2
				Q.append(j)
	return V

def reade():
	(u, v) = readinti()
	return (u - 1, v - 1)

def case():
	input()
	(n, m) = readinti()
	E = [reade() for _ in range(m)]
	return lstr(solve(n, m, E))

def main():
	t = readint()
	print('\n'.join((case() for _ in range(t))))

def readint():
	return int(input())

def readinti():
	return map(int, input().split())

def readintt():
	return tuple(readinti())

def readintl():
	return list(readinti())

def readinttl(k):
	return [readintt() for _ in range(k)]

def readintll(k):
	return [readintl() for _ in range(k)]

def lstr(l):
	return ' '.join(map(str, l))

def llstr(ll):
	return '\n'.join(map(lstr, ll))

def log(*args, **kwargs):
	print(*args, **kwargs, file=sys.__stderr__)
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def find_SCC(graph):
	(SCC, S, P) = ([], [], [])
	depth = [0] * len(graph)
	stack = list(range(len(graph)))
	while stack:
		node = stack.pop()
		if node < 0:
			d = depth[~node] - 1
			if P[-1] > d:
				SCC.append(S[d:])
				del S[d:], P[-1]
				for node in SCC[-1]:
					depth[node] = -1
		elif depth[node] > 0:
			while P[-1] > depth[node]:
				P.pop()
		elif depth[node] == 0:
			S.append(node)
			P.append(len(S))
			depth[node] = len(S)
			stack.append(~node)
			stack += graph[node]
	return SCC[::-1]
for _ in range(int(input())):
	input()
	(n, m) = [int(i) for i in input().split()]
	g = [[] for i in range(n)]
	scc = []
	for i in range(m):
		(u, v) = [int(i) - 1 for i in input().split()]
		g[u].append(v)
		if u == v:
			scc.append([u])
	s1 = find_SCC(g)
	for i in s1:
		if len(i) > 1:
			scc.append(i[:])
	infinite = [0] * n
	for i in scc:
		for j in i:
			infinite[j] = -1
	vis = [0] * n
	stack = [0]
	vis[0] = 1
	if infinite[0]:
		vis[0] = -1
		stack1 = [0]
		while len(stack1):
			curr1 = stack1.pop()
			for i1 in g[curr1]:
				if vis[i1] != -1:
					vis[i1] = -1
					stack1.append(i1)
	while stack:
		curr = stack.pop()
		for i in g[curr]:
			if not vis[i]:
				stack.append(i)
				vis[i] = 1
				if infinite[i]:
					vis[i] = -1
					stack1 = [i]
					while len(stack1):
						curr1 = stack1.pop()
						for i1 in g[curr1]:
							if vis[i1] != -1:
								vis[i1] = -1
								stack1.append(i1)
			elif vis[i] == 1:
				vis[i] += 1
				stack.append(i)
	print(*vis)


import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

def scc_dfs1(s, links, status, postorder):
	stack = [s]
	status[s] = 0
	while stack:
		v = stack[-1]
		limit = len(links[v])
		while status[v] < limit:
			u = links[v][status[v]]
			status[v] += 1
			if status[u] != -1:
				continue
			stack.append(u)
			status[u] = 0
			break
		else:
			stack.pop()
			postorder.append(v)
	return

def scc_dfs2(s, rev_links, status):
	stack = [s]
	status[s] = -1
	scc = [s]
	while stack:
		v = stack.pop()
		for u in rev_links[v]:
			if status[u] != -1:
				stack.append(u)
				status[u] = -1
				scc.append(u)
	return scc

def strongly_connected_components(n, links, rev_links):
	status = [-1] * n
	postorder = []
	for v in range(n):
		if status[v] != -1:
			continue
		scc_dfs1(v, links, status, postorder)
	postorder.reverse()
	sccs = []
	for v in postorder:
		if status[v] == -1:
			continue
		sccs.append(scc_dfs2(v, rev_links, status))
	return sccs

def main():
	t = int(input())
	INF = pow(10, 18)
	for _ in range(t):
		dummy = input()
		(n, m) = map(int, input().split())
		G = [[] for _ in range(n)]
		RG = [[] for _ in range(n)]
		self_v = set([])
		for _ in range(m):
			(a, b) = map(int, input().split())
			a -= 1
			b -= 1
			G[a].append(b)
			RG[b].append(a)
			if a == b:
				self_v.add(a)
		TT = strongly_connected_components(n, G, RG)
		ans = [0] * n
		ans[0] = 1
		for cluster in TT:
			if len(cluster) > 1:
				Flag = True
				for p in cluster:
					if not Flag:
						break
					for pre in RG[p]:
						if ans[pre] == -1:
							Flag = False
							break
						ans[p] += ans[pre]
						if ans[p] > 0:
							Flag = False
							break
				if not Flag:
					for p in cluster:
						ans[p] = -1
				else:
					for p in cluster:
						ans[p] = 0
			else:
				p = cluster[0]
				if p in self_v:
					Flag = True
					for pre in RG[p]:
						if ans[pre] == -1:
							Flag = False
							break
						ans[p] += ans[pre]
						if ans[p] > 0:
							Flag = False
							break
					if not Flag:
						ans[p] = -1
				else:
					for pre in RG[p]:
						if ans[pre] == -1:
							ans[p] = -1
							break
						else:
							ans[p] += ans[pre]
							ans[p] = min(ans[p], 2)
		print(*ans)
main()


import sys
import getpass
from collections import Counter, defaultdict, deque
input = sys.stdin.readline
M9 = 10 ** 9 + 7
(yes, no) = ('YES', 'NO')
MAXINT = sys.maxsize
OFFLINE_TEST = getpass.getuser() == 'hkmac'

def log(*args):
	if OFFLINE_TEST:
		print('\x1b[36m', *args, '\x1b[0m', file=sys.stderr)

def solve(*args):
	if OFFLINE_TEST:
		log('----- solving ------')
		log(*args)
		log('----- ------- ------')
	return solve_(*args)

def read_matrix(rows):
	return [list(map(int, input().split())) for _ in range(rows)]

def read_strings(rows):
	return [input().strip() for _ in range(rows)]

def minus_one(arr):
	return [x - 1 for x in arr]

def minus_one_matrix(mrr):
	return [[x - 1 for x in row] for row in mrr]
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					if stack:
						stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

def solve_(n, edges):
	parents = set()
	visitable = set()
	cycles = set()
	duals = set()
	g = defaultdict(set)
	for (a, b) in edges:
		g[a].add(b)

	@bootstrap
	def dfs(cur):
		visitable.add(cur)
		parents.add(cur)
		for nex in g[cur]:
			if nex in parents:
				cycles.add(nex)
				continue
			if nex in visitable:
				duals.add(nex)
				continue
			yield dfs(nex)
		parents.discard(cur)
		yield
	dfs(0)
	stack = list(duals)
	while stack:
		cur = stack.pop()
		for nex in g[cur]:
			if nex in duals:
				continue
			duals.add(nex)
			stack.append(nex)
	stack = list(cycles)
	while stack:
		cur = stack.pop()
		for nex in g[cur]:
			if nex in cycles:
				continue
			cycles.add(nex)
			stack.append(nex)
	res = [0] * n
	for i in range(n):
		if i in cycles:
			res[i] = -1
			continue
		if i in duals:
			res[i] = 2
			continue
		if i in visitable:
			res[i] = 1
			continue
	return res
res_lst = []
for case_num in range(int(input())):
	srr = input().strip()
	(n, m) = list(map(int, input().split()))
	edges = read_matrix(m)
	edges = minus_one_matrix(edges)
	res = solve(n, edges)
	res = ' '.join((str(x) for x in res))
	res_lst.append(res)
print('\n'.join(res_lst))


def naiveSolve():
	return
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

def main():
	t = int(input())
	allans = []
	for _ in range(t):
		input()
		(n, m) = readIntArr()
		adj = [[] for __ in range(n + 1)]
		for __ in range(m):
			(u, v) = readIntArr()
			adj[u].append(v)
		visitCnts = [0] * (n + 1)
		revisitedNodeCyc = set()
		revisitedNodeNonCyc = set()
		path = set()

		@bootstrap
		def dfs1(node):
			for nex in adj[node]:
				if visitCnts[nex] == 1:
					if nex in path:
						revisitedNodeCyc.add(nex)
					else:
						revisitedNodeNonCyc.add(nex)
				else:
					visitCnts[nex] += 1
					path.add(nex)
					yield dfs1(nex)
					path.remove(nex)
			yield None
		path.add(1)
		visitCnts[1] = 1
		dfs1(1)

		@bootstrap
		def dfsCyc(node):
			for nex in adj[node]:
				if visitCnts[nex] == 1:
					visitCnts[nex] = -1
					yield dfsCyc(nex)
			yield None
		for cycNode in revisitedNodeCyc:
			if visitCnts[cycNode] == 1:
				visitCnts[cycNode] = -1
				dfsCyc(cycNode)

		@bootstrap
		def dfsNonCyc(node):
			for nex in adj[node]:
				if visitCnts[nex] == 1:
					visitCnts[nex] = 2
					yield dfsNonCyc(nex)
			yield None
		for nonCycNode in revisitedNodeNonCyc:
			if visitCnts[nonCycNode] == 1:
				visitCnts[nonCycNode] = 2
				dfsNonCyc(nonCycNode)
		visitCnts.pop(0)
		allans.append(visitCnts)
	multiLineArrayOfArraysPrint(allans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x):
	print('{}'.format(x))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
MOD = 998244353
from math import gcd, floor, ceil
for _abc in range(1):
	main()