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 PI 3.14159265358979323
#define ll long long int
#define vi vector <int>
#define vl vector <ll>
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000007
ll power(ll a, ll b) { //a^b
	ll res = 1;
	a = a % MOD;
	while (b > 0) {
		if (b & 1) {res = (res * a) % MOD; b--;}
		a = (a * a) % MOD;
		b >>= 1;
	}
	return res;
}

ll gcd(ll a, ll b) {return (b == 0) ? a : gcd(b, a % b);}

vector <vl> adj(400005);
vector <vl> adjt(400005);
vl vis(400005);
vl vis2(400005);

vl top;

void dfs(ll u) {
	for (auto i : adj[u]) {
		if (vis[i] == 0) {
			vis[i] = 1;
			dfs(i);
		}
	}
}

void dfs2(ll u) {
	for (auto i : adj[u]) {
		if (!vis2[i]) {
			vis2[i] = 1;
			dfs2(i);
		}
	}
	top.pb(u);
}

int main() {
#ifndef ONLINE_JUDGE
	// for getting input from input.txt
	freopen("input.txt", "r", stdin);
	// for writing output to output.txt
	freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll t;
	cin >> t;
	while (t--) {
		ll n, m;
		cin >> n >> m;
		top.clear();
		for (ll i = 0; i < n; i++) {
			adj[i].clear();
			vis[i] = 0;
			vis2[i] = 0;
			adjt[i].clear();
		}
		vector <pair<ll, ll>> edges;
		for (ll i = 0; i < m; i++) {
			ll u, v;
			cin >> u >> v;
			u--;
			v--;
			adj[u].pb(v);
			adjt[v].pb(u);
			edges.pb({u, v});
		}
		vis[0] = 1;
		dfs(0);
		for (ll i = 0; i < n; i++) {
			if (!vis2[i]) {
				vis2[i] = 1;
				dfs2(i);
			}
		}
		reverse(all(top));
		vl ans(n, 0);
		map <ll, ll> pos;
		for (ll i = 0; i < n; i++) {
			if (vis[i])
				ans[i] = 1;
			pos[top[i]] = i;
		}
		set <ll> cyc;
		for (auto i : edges) {
			if (pos[i.ff] < pos[i.ss])
				continue;
			if (vis[i.ff] && ans[i.ff] != -1) {
				ans[i.ff] = -1;
				cyc.insert(i.ff);
			}
			if (vis[i.ss] && ans[i.ss] != -1) {
				ans[i.ss] = -1;
				cyc.insert(i.ss);
			}
		}
		queue <ll> q;
		for (auto i : cyc)
			q.push(i);
		while (!q.empty()) {
			ll cur = q.front();
			q.pop();
			for (auto i : adj[cur]) {
				if (ans[i] != -1) {
					ans[i] = -1;
					q.push(i);
				}
			}
		}
		vl cnt(n, 0);
		cnt[0] = 1;
		for (ll i = pos[0]; i < n; i++) {
			ll cur = top[i];
			if (!vis[cur])
				continue;
			for (auto j : adj[cur]) {
				if (cnt[j] == 0)
					cnt[j] = cnt[cur];
				else
					cnt[j] = 2;
			}
		}
		for (ll i = 0; i < n; i++) {
			if (ans[i] == 1 && cnt[i] > 1)
				ans[i] = 2;
			cout << ans[i] << " ";
		}
		cout << "\n";
	}
}