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;

typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 4e5 + 10;
const ll mod = 1e9+7;

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

int t, n, m, c;
vector < int > out[maxn], in[maxn];
queue < int > q;
vector < int > topo;
bool loop[maxn], inf[maxn];
int ans[maxn], col[maxn], sz[maxn];

void sfd(int v){
	col[v] = c;
	for(auto u : in[v]) if(!col[u])
		sfd(u);
}
void dfs(int v){
	col[v] = 1;
	for(auto u : out[v]) if(!col[u])
		dfs(u);
	topo.pb(v);
}

vector < int > adj[maxn];
int lsl[maxn];
int reach[maxn];

int32_t main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> t;
	while(t --){
		cin >> n >> m;
		for(int i = 1 ; i <= n ; i ++)
			out[i].clear(), in[i].clear(), ans[i] = 0 , loop[i] = 0 , col[i] = 0;
		for(int i = 1 ; i <= n ; i ++)lsl[i] = 0;
		for(int i = 1 ; i <= m ; i ++){
			int u, v;
			cin >> u >> v;
			if(u ^ v)out[u].pb(v), in[v].pb(u);
			if(u == v)loop[u] = 1;
		}
		topo.clear();
		for(int i = 1 ; i <= n ; i ++ ) if(!col[i]) dfs(i);
		reverse(topo.begin() , topo.end());
		for(int i = 1 ; i <= n ; i ++)col[i] = 0;
		c = 0;
		for(auto v : topo)
			if(!col[v])
				++c , sfd(v);
		for(int i = 1 ; i <= c ; i ++)
			sz[i] = 0, inf[i] = 0 , adj[i].clear();
		for(int i = 1 ; i <= n ; i ++)
			sz[col[i]] ++, sz[col[i]] += loop[i];
		for(int i = 1 ; i <= c ; i ++)
			if(sz[i] > 1)inf[i] = 1;
		for(int i = 1 ; i <= n ; i ++)
			for(auto u : out[i])if(col[u] ^ col[i])	
				adj[col[i]].pb(col[u]);
		for(int i = 1 ; i <= c ; i ++)
			sort(adj[i].begin(), adj[i].end()),
			adj[i].resize(unique(adj[i].begin(), adj[i].end()) - adj[i].begin());
		for(int i = 1 ; i <= c ; i ++)reach[i] = 0;
		reach[col[1]] = 1;
		q.push(col[1]);
		while(q.size()){
			int v = q.front();
			q.pop();
			for(auto u : adj[v])if(!reach[u])
				reach[u] = 1 , q.push(u);
		}
		for(int i = 1 ; i <= c ; i ++)if(reach[i])
			for(auto u : adj[i]){
			lsl[u] ++;}
		q.push(col[1]);
		ans[col[1]] = ((inf[col[1]]) ? -1 : 1);
		while(q.size()){
			int v = q.front();
			q.pop();
			for(auto u : adj[v]){
				lsl[u] --;
				if(ans[u] == 0){
					ans[u] = ans[v];
					if(inf[u])ans[u] = -1;
				}
				else if(ans[u] == 1){
					if(ans[v] == -1)ans[u] = -1;
					else ans[u] = 2;
				}
                else if(ans[u] == 2){
                    if(ans[v] == -1)ans[u] = -1;
                }
				if(lsl[u] == 0)q.push(u);
				if(inf[u])ans[u] = -1;
			}
		}
		for(int i = 1 ; i <= n ; i ++)
			cout << ans[col[i]] << ' ';
		cout << endl;	
	}
	return(0);
}