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 <cmath>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int t,n,m,cnt,nnt,time_flag,h[808080],o[808080],o2[808080],h2[808080],in[808080],vis[808080],ans[808080],dfn[808080],low[808080],cir[808080],nmnode[808080],nmval[808080],nmcir[808080];
stack<int>st;

struct graph
{
    int from,to,next,val;
}e[808080],e2[808080];

void add(int x,int y)
{
    e[++cnt].next = h[x];
    e[cnt].from = x;
    e[cnt].to = y;
    h[x] = cnt;
}

void add2(int x,int y)
{
    e2[++cnt].next = h2[x];
    e2[cnt].from = x;
    e2[cnt].to = y;
    h2[x] = cnt;
}

void topo()
{
    for(int i = 1 ; i <= n ; ++i)
        vis[i] = 0;
    for(int i = 1 ; i <= cnt ; ++i){
        int l = e2[i].from;
        int r = e2[i].to;
        in[r]++;
        ///cout << l << "     " << r << endl ;
    }
    queue<int>q;
    q.push(nmnode[1]);
    ans[nmnode[1]] = 1;
    while(!q.empty()){
        int now = q.front();
        q.pop();
        vis[now] = 1;
        ans[now] = (nmcir[now]==1 ? -1 : ans[now]);
        for(int i = h2[now] ; i ; i = e2[i].next){
            int v = e2[i].to;
            if(!vis[v]){
                in[v]--;
                if(!in[v]){
                    q.push(v);
                }
                ///cout << now << "??" << v << endl ;
                ///cout << cir[now] << " ?? " << cir[v] << " ?? " << ans[v] << endl ;
                ans[v] = ((ans[now]==-1 || nmcir[v]==1 || ans[v]==-1) ? -1 : min(2,ans[v] + ans[now]) );
            }
        }

    }
}

void tarjan(int now)
{
    o[now] = 1;
    dfn[now] = low[now] = (++time_flag);
    vis[now] = 1;
    st.push(now);
    for(int i = h[now] ; i ; i = e[i].next){
        int v = e[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[now] = min(low[now],low[v]);    ///能走通的话要对比的时下个点的low，也就是能回溯的最早点，而不是dfn
        }
        else if(vis[v]){///vis是表示一条线搜下来的，判断是否在一个环里，vis之后会去掉，不能用dfn代替
            low[now] = min(low[now],dfn[v]);    ///如果碰到的点已经来过，说明找到了环
        }
    }
    if(dfn[now] == low[now]){
        int y;
        ++nnt;
        do{
            y = st.top();
            st.pop();
            nmnode[y] = nnt;
            nmval[nnt]++;
            vis[y] = 0;
        }while(y != now);
    }
}

int main()
{
    ios::sync_with_stdio(false);
	cin >> t ;
	while(t--){
        cnt = nnt = time_flag = 0;
        cin >> n >> m ;
        int l,r;
        for(int i = 1 ; i <= m ; ++i){
            cin >> l >> r ;
            add(l,r);
            if(l == r)cir[l] = 1;
        }
        tarjan(1);
        for(int i = 1 ; i <= n ; ++i)
            if(cir[i])nmcir[nmnode[i]] = 1;
        for(int i = 1 ; i <= n ; ++i)
            if(nmval[nmnode[i]] >= 2)
                nmcir[nmnode[i]] = 1;
        cnt = 0 ;
        for(int i = 1 ; i <= n ; ++i)
            h2[i] = 0;
        for(int i = 1 ; i <= m ; ++i){
            l = nmnode[e[i].from];
            r = nmnode[e[i].to];
            if(l && r && l != r)add2(l,r);
            ///cout << l << "?" << r << endl ;
        }
        topo();
        for(int i = 1 ; i <= n ; ++i){
            if(ans[nmnode[i]] == 0)cout << 0 << " " ;
            else if(ans[nmnode[i]] == 1)cout << 1 << " " ;
            else if(ans[nmnode[i]] >= 2)cout << 2 << " " ;
            else if(ans[nmnode[i]] == -1)cout << -1 << " " ;
        }
        cout << endl ;
        for(int i = 1 ; i <= n ; ++i)
            o[i] = h[i] = vis[i] = ans[i] = dfn[i] = low[i] = cir[i] = in[i] = nmcir[i] = nmval[i] = nmnode[i] = 0;
        while(!st.empty())st.pop();
	}
	return 0;
}