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;
const int N = 4e5 + 10, M = N * 2;
typedef long long ll;
typedef pair<ll, ll> pii;
#define endl '\n'
// 1 到当前点：
// 0：没有路
// 1：一条路
// 2：多条路
// -1：无线条路
// 与1号点在同一强连通分量中的点：-1
// 搜一遍，每个点最多两边
int n, m, t;
int h[N], ne[M], e[M], idx;
void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int dfn[N], low[N], timestamp;
stack<int> s;
bool in_s[N], st[N];
int scc_cnt;
int a[N];
void tarjan(int u){
    dfn[u] = low[u] = ++timestamp;
    s.push(u); in_s[u] = 1;
    for(int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        if(j == u) a[j] = -1;
        if(!dfn[j]){
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }else if(in_s[j]) low[u] = min(low[u], dfn[j]);
    }
    if(dfn[u] == low[u]){
        ++scc_cnt;
        int y;
        do{
            y = s.top(); s.pop();
            in_s[y] = 0;
            if(y != u) a[y] = -1;
        }while(y != u);
    }
}

void init(){
    while (!s.empty()) s.pop();
    for(int i = 1; i <= n + 5; i++){
        timestamp = scc_cnt = dfn[i] = low[i] = st[i] = a[i] = 0;
        h[i] = -1;
    }
}
void cal(int u, int k){
    if (k == -1) a[u] = -1;
    if (a[u] == -1) return;
    a[u] = min(a[u] + k, 2);
}
void dfs1(int x){
    if(st[x]) return;
    st[x] = 1;
    for(int i = h[x]; ~i; i = ne[i]){
        int j = e[i];
        cal(j, a[x]);
        dfs1(j);
    }
}
void dfs2(int x){
    for(int i = h[x]; ~i; i = ne[i]){
        int j = e[i];
        if(a[j] == 1){
            a[j] = 2;
            dfs2(j);
        }
    }
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>m;
        init();
        for(int i = 1; i <= m; i++){
            int a, b; cin>>a>>b;
            add(a, b);
        }
        tarjan(1);
       // for(int i = 1; i <= n; i++) cout<<a[i]<<" ";
        cal(1, 1);
        for (int i = 1; i <= n; i++)
            if (a[i] == -1) dfs1(i);
        dfs1(1);
        for(int i = 1; i <= n; i++)
            if(a[i] == 2) dfs2(i);
        for(int i = 1; i <= n; i++) cout<<a[i]<<" ";
        cout<<endl;
    }
    return 0;
}