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>
#define pb push_back
#define ll long long
#define ull unsigned long long
#define mp make_pair
#define si short int
#define speed ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pill pair<ll,ll>
#define f first
#define s second
#define pilc pair<ll,char>
#define all(a) (a).begin(),(a).end()
#define rep(s,e,step) for(int i = (s); i < (e) ; i += step)
#define vrep(s,e,step) for(int j = (s); j < (e) ; j += step)
#define ex exit(0) 
#define sz(a) (ll)(a).size()
#define triple pair<pill, ll>
#define pinode pair<node*, node*>
#define quadra pair<pill, pill>
#define ld double
using namespace std;
 
const ll N = 1e6 + 10;
const ll M = 1e14;
const ll big = 1e17;
const ll hsh2 = 1964325029 ;
const long long mod = 998244353;
const long double EPS = 1e-9;
const ll block = 1e14;
const ll shift = 2e3;
const ld pi = acos(-1.0);



ll ta, n, m;
bool was[N];
vector<ll> g[N], bg[N], ng[N], tps;

void dfs(ll v) {
	was[v] = 1;
	for(auto u : g[v]) {
		if(!was[u])
			dfs(u);			
	}      
	tps.pb(v);
}

ll col[N], cnt = 1, cont[N];
vector<ll> comp;

void bdfs(ll v) {
 	was[v] = 0;
 	col[v] = cnt;
	comp.pb(v); 	
 	for(auto u : bg[v]) {
 		if(was[u])
 			bdfs(u);
 	}
}


bool cycle[N], ncyc[N];

void cond() {	
	for(int i = 1; i <= n; i++)
		if(!was[i])
			dfs(i);
	reverse(tps.begin(), tps.end());
	for(auto u : tps) {
	    if(!was[u])continue;
		bdfs(u);
		if(comp.size() == 1) {
			if(cycle[comp.back()])
				ncyc[cnt] = 1;	
		} else ncyc[cnt] = 1;
		comp.clear();
		cnt++;
	}
	for(int i = 1; i <= n; i++) {
		for(auto u : g[i]) {
			if(col[u] == col[i])continue;
			ng[col[i]].pb(col[u]);	
		}
	}
}


ll answ[N];

void bfs() {
	for(int i = 1; i < cnt; i++)
		answ[i] = 4;
	queue<ll> x;
	if(ncyc[col[1]])
		answ[col[1]] = -1;
	else
		answ[col[1]] = 1;
	x.push(col[1]);
	was[col[1]] = 1;
	while(x.size()) {
		ll v = x.front();
		x.pop();
		for(auto u : ng[v]) {
			if(!was[u])
				was[u] = 1, x.push(u);
		}
	}
	for(int i = 1; i < cnt; i++) {
		if(was[i]) {
			for(auto u : ng[i])
				cont[u]++;						
		}
	}
	vector<ll> activate;
	for(int i = 1; i < cnt; i++) {
		if(was[i] && cont[i] == 0) {
			activate.pb(i);
		}
		was[i] = 0;
	}
	ll cur = 0;
	while(cur < activate.size()) {
		ll v = activate[cur];
		for(auto u : ng[v]) {
			if(!was[u]) {
				was[u] = 1;
				answ[u] = answ[v];
				cont[u]--;
				if(ncyc[u])
					answ[u] = -1;
			}
			else {
				if(answ[v] == -1)
					answ[u] = -1;
			 	else if(answ[u] == 1 && answ[v] != -1)
			 		answ[u] = 2;			 			
				cont[u]--;
			}
			if(cont[u] == 0)
				activate.pb(u);
		}
		cur++;
	}
}

int main() {                                                       
	speed;
	cin >> ta;
	while(ta--) {
		cin >> n >> m;
		for(int i = 1; i <= n; i++)
			g[i].clear(), ng[i].clear(), bg[i].clear(), cycle[i] = ncyc[i] = was[i] = answ[i] = col[i] = cont[i] = 0;
		tps.clear();
		for(int i = 1, a, b; i <= m; i++) {
			cin >> a >> b;
			if(a == b)cycle[a] = 1;
			g[a].pb(b);
			bg[b].pb(a);						
		}
		cond();
		bfs();
		for(int i = 1; i <= n; i++)
			cout << (answ[col[i]] == 4 ? 0 : answ[col[i]]) << " ";
		cout << '\n';	
	}
}
/*                  
4
4 6 1 9
2 5 3 2 
*/