Problem: 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.

<image>

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 ≤ t ≤ 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 ≤ n ≤ 4 ⋅ 10^5, 0 ≤ m ≤ 4 ⋅ 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 ≤ a_i, b_i ≤ 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 ≠ j).

The sum of n over all test cases does not exceed 4 ⋅ 10^5. Similarly, the sum of m over all test cases does not exceed 4 ⋅ 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.

Example

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 

Solution (in CPP):

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

#define INF 1234567890
#define ll long long

int T;
int N, M, P;
vector<int> g[400401], h[400401];
bool vis[400401], reach[400401], loop[400401];
vector<int> st;
int myscc[400401], sz[400401], dp[400401];

void DFS(int n)
{
	vis[n] = true;
	for(int next : g[n])
	{
		if (vis[next]) continue;
		DFS(next);
	}
	st.push_back(n);
}
void DFS2(int n)
{
	vis[n] = true;
	for(int next : h[n])
	{
		if (vis[next]) continue;
		DFS2(next);
	}
	myscc[n] = P;
	sz[P]++;
}
void DFS3(int n)
{
	vis[n] = true;
	for(int next : g[n])
	{
		if (vis[next]) continue;
		DFS3(next);
	}
}

bool isScc(int i)
{
	return (sz[myscc[i]] >= 2 || loop[i]);
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	cin >> T;
	while(T--)
	{
		cin >> N >> M;
		// clear
		P = 0;
		for(int i=1; i<=N; i++)
		{
			g[i].clear();
			h[i].clear();
		}
		memset(vis, 0, sizeof(bool)*(N+1));
		memset(reach, 0, sizeof(bool)*(N+1));
		memset(loop, 0, sizeof(bool)*(N+1));
		st.clear();

		for(int i=0; i<M; i++)
		{
			int a, b;
			cin >> a >> b;
			if (a == b) { loop[a] = true; continue; }
			g[a].push_back(b);
			h[b].push_back(a);
		}

		DFS(1);
		for(int i=1; i<=N; i++)
			if (vis[i])
				reach[i] = true;

		for(int i=1; i<=N; i++)
			if (!vis[i])
				DFS(i);

		memset(vis, 0, sizeof(bool)*(N+1));
		reverse(st.begin(), st.end()); // DFS 종료 역순 = 위상정렬순
		for(int n : st)
		{
			if (vis[n]) continue;
			sz[P] = 0;
			DFS2(n);
			P++;
		}

		memset(vis, 0, sizeof(bool)*(N+1));
		for(int i=1; i<=N; i++)
			if (reach[i] && isScc(i) && !vis[i])
				DFS3(i); // 1 -> scc -> x가 가능한가?

		memset(dp, 0, sizeof(int)*(N+1)); // 0,1,2+
		dp[1] = 1;
		for(int n : st)
		{
			if (dp[n] > 2) dp[n] = 2;
			for(int next : g[n])
				dp[next] += dp[n];
		}

		for(int i=1; i<=N; i++)
		{
			if (reach[i] == false) cout << "0 ";
			else if (vis[i]) cout << "-1 ";
			else if (dp[i] >= 2) cout << "2 ";
			else cout << "1 ";
		}
		cout << "\n";
	}
	return 0;
}