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;
using ll = long long;

const int mxN = 1e6 + 5, mod = 1e9 + 7, LOG = 20;

int n, m, pet[mxN], ans[mxN];

bool used[mxN], was[mxN];

vector <int> adj[mxN], radj[mxN], comp, c;

void dfs1(int v) {
	used[v] = 1;
	for (auto to : adj[v]) {
		if (!used[to]) dfs1(to);
	} comp.push_back(v);
}

void dfs2(int v) {
	c.push_back(v);
	used[v] = 1;
	for (auto to : radj[v]) {
		if (!used[to]) dfs2(to);
	}
}

void dfs3(int v, int chel) {
	was[v] = 1; ans[v] = chel;
	for (auto to : adj[v]) {
		if (!was[to]) dfs3(to, chel);
	}
}

vector <int> mda;

void dfs4(int v) {
	used[v] = 1;
	for (auto to : adj[v]) {
		if (!used[to]) dfs4(to);
		else if (ans[to] != -1) mda.push_back(to);
	}
}

void solve() {
	cin >> n >> m;
	// clear
	mda.clear(); comp.clear(); 
	for (int i = 1; i <= n; ++i) used[i] = was[i] = pet[i] = ans[i] = 0, adj[i].clear(), radj[i].clear();
	for (int i = 1, u, v; i <= m; ++i) {
		cin >> u >> v;
		if (u == v) pet[u] = 1;
		else {
			adj[u].push_back(v);
			radj[v].push_back(u);
		}		
	}
	dfs1(1);
	for (int i = 1; i <= n; ++i) used[i] = 1;
	reverse(comp.begin(), comp.end());
	for (auto x : comp) used[x] = 0;
	for (auto v : comp) {
		if (!used[v]) {
			dfs2(v);
			sort(c.begin(), c.end()); 
			if (c.size() > 1) {
				if (c.size() > 1) {
					for (auto x : c) {
						if (!was[x]) dfs3(x, -1);
					}
				}
			}
			else if (pet[c[0]] && !was[c[0]]) dfs3(c[0], -1); 
			c.clear();
		}
	}
	for (int i = 1; i <= n; ++i) used[i] = 0;
	dfs4(1);
	for (auto x : mda) {
		if (!was[x]) dfs3(x, 2); 
	}
	for (auto x : comp) {
		if (!was[x]) ans[x] = 1;	
	}
	for (int i = 1; i <= n; ++i) cout << ans[i] << ' ';
}

int main() {
	ios :: sync_with_stdio(false), cin.tie(nullptr);
	int t;
	cin >> t;
	while (t--) {
		solve();
		cout << '\n';
	}
	return 0;
}