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 forr(i,a,b) for(int i=(a);i<(b);i++)
#define forn(i,n) forr(i,0,n)
#define dforn(i,n) for(int i=n-1;i>=0;i--)
#define forall(it,v) for(auto it=v.begin();it!=v.end();it++)
#define sz(c) ((int)c.size())
#define rsz resize
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fst first
#define snd second

#ifdef ANARAP
#define MAXN 4005
#else
#define MAXN 400005
#endif

using namespace std;

typedef long long ll;
typedef pair<int,int> ii;


int n,m;
vector<int> dist, cant;
int d[MAXN];
vector<int> G[MAXN],gt[MAXN]; //Limpiar si se corre mas de una vez
set<int> g[MAXN];
//nodos 0...N-1 ; componentes 0...cantcomp-1
int comp[MAXN],N,cantcomp,used[MAXN];
stack<int> pila;
int cont = 0;
void add(int a, int b){ G[a].pb(b);gt[b].pb(a);}
void dfs1(int nodo)
{
	used[nodo]=1;
	forall(it,G[nodo]) if(!used[*it]) dfs1(*it);
	pila.push(nodo);
}
void dfs2(int nodo)
{
	used[nodo]=2;
	comp[nodo]=cantcomp-1;
	forall(it,gt[nodo]) if(used[*it]!=2) dfs2(*it);
}
void kosaraju()
{
	cantcomp=0;
	memset(used,0,sizeof(used));
	forn(i,N) if(!used[i]) dfs1(i);
	while(!pila.empty())
	{
		if(used[pila.top()]!=2)
		{
			cantcomp++;
			dfs2(pila.top());
		}
		pila.pop();
	}
}

void bfs(int node){
	forn(i,n) used[i] = 0;
	used[node] = 1;
	queue<int> q;
	q.push(node);
	while(!q.empty()){
		int aux = q.front();
		q.pop();
		forall(it, G[aux]){
			if(used[*it] == 0){
				used[*it] = 1;
				q.push(*it);
			}
		}
	}
}

void topsort(int node){
	queue<int> q;
	q.push(node);
	while(!q.empty()){
		int aux = q.front();
		q.pop();
		if(cant[aux] >= 2) dist[aux] = INT_MAX;
		else if(dist[aux] == -1) dist[aux] = 1;
		forall(it, g[aux]){
			d[*it]--;
			if(dist[*it] != INT_MAX){
				if(dist[aux] == INT_MAX) dist[*it] = INT_MAX;
				else dist[*it] = max(0, dist[*it])+ dist[aux];
			}
			if(d[*it] == 0)q.push(*it);
		}
	}
}

int main()
{
	#ifdef ANARAP
		freopen("input.in", "r", stdin);
		//freopen("output.out", "w", stdout);
		unsigned t0, t1; t0=clock();
	#endif
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t; cin >> t;
	forn(T,t){
		cin >> n >> m;
		N=n;
		dist.clear();dist.resize(n);
		cant.clear(); cant.resize(n);
		forn(i,n) dist[i] = -1;
		vector<int> setInf;
		forn(i,m){
			int a,b; cin >> a >> b;
			a--; b--;
			if(a!=b) add(a,b);
			else setInf.pb(a);
		}
		kosaraju();
		bfs(0);
		forn(i,n) d[i] = 0;
		forall(it, setInf) if(used[*it]) dist[comp[*it]] = INT_MAX;
		forn(i,n){
			if(used[i]){
				cant[comp[i]]++;
				forall(it, G[i]) if(comp[*it] != comp[i]) 
				{  
					if(g[comp[i]].count(comp[*it])) continue;
					g[comp[i]].insert(comp[*it]);
					d[comp[*it]]++;
				}
			}
		}
		topsort(comp[0]);
		forn(i,n) assert(d[comp[i]] == 0);
		forn(i,n){
			cont++;
			if(dist[comp[i]] == -1) cout << 0 << " ";
			else if(dist[comp[i]] == 1) cout << 1 << " ";
			else if(dist[comp[i]] == INT_MAX) cout << -1 << " ";
			else cout << 2 << " ";
		}
		cout << '\n';
		forn(i,n) G[i].clear(), gt[i].clear(), g[i].clear();
	}
	
	#ifdef ANARAP
	t1 = clock();double time = (double(t1-t0)/CLOCKS_PER_SEC); cout << "Execution Time: " << time << endl;
	#endif
	return 0;
}