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:
 /* ****Yash_mittal**** */

#include <bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define ppb         pop_back
#define endl        '\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define pqi         priority_queue<ll>
#define pqd         priority_queue<ll,vi,greater<ll>>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)  for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define ppii        3.141592653
using namespace std;

#define N 100005
// bool prime[1000001];
// vi v;
// int d[10000000];
// void sieve()
// {
//     memset(d, -1, sizeof(d));
//     d[0]=1;
//     d[1]=1;
//     prime[0]=true;
//     prime[1]=true;
//     for(ll i=2;i<=1000000;i++)
//     {
//         d[i]=i;
//         if(prime[i]==false)
//         {
//             v.pb(i);
//             // cnt[i] = cnt[i-1]+1;
//             for(ll j=i*i;j<=1000000;j+=i){
//                 prime[j]=true;
//                 d[j]=i;
//             }
//         }
//     }
// }
ll gcd(ll a,ll b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}
ll powx(ll a,ll p) 
{
    ll ans=1;
    for(int i=0;i<p;i++)
        ans*=a;
    return ans;
}
vi adj[4*N];
int vis[4*N],vis1[4*N],vis2[4*N];
int ans[4*N],par[4*N];
vector<pii> cycle;
vi two;
void dfs(int x,int p)
{
    vis[x]=1;
    ans[x]=1;
    par[x] = p;
    for(auto i:adj[x])
    {
        if(!vis[i])
        {
            dfs(i,x);
        }
        else if(vis[i]==1)
        {
            ans[x] = -1;
            ans[i] = -1;
            cycle.pb({x,i});
        }
        else
        {
            ans[i] = 2;
            two.pb(i);
        }
    }
    vis[x]=2;
}
void dfs1(int x)
{
    vis1[x]=1;
    ans[x]=-1;
    for(auto i:adj[x])
    {
        if(!vis1[i])
            dfs1(i);
    }
}
void dfs2(int x)
{
    vis2[x]=1;
    ans[x]=2;
    for(auto i:adj[x])
    {
        if(!vis2[i])
            dfs2(i);
    }
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            adj[i].clear();
            vis[i]=0;
            vis1[i]=0;
            vis2[i]=0;
            ans[i]=0;
        }
        cycle.clear();
        two.clear();
        vi v;
        for(int i=0;i<m;i++)
        {
            int a,b;
            cin>>a>>b;
            if(a!=b)
                adj[a].pb(b);
            else
                v.pb(a);
        }
        dfs(1,0);
        for(auto i:two)
        {
            if(!vis2[i])
                dfs2(i);
        }
        for(auto i:cycle)
        {
            int x = i.F;
            if(!vis1[x])
                dfs1(x);
        }
        vi v2;
        for(auto i:v)
        {
            if(vis[i])
                v2.pb(i);
        }
        for(auto i:v2)
        {
            if(!vis1[i])
                dfs1(i);
        }
        for(int i=1;i<=n;i++)
            cout<<ans[i]<<" ";
        cout<<endl;
    }
    return 0;
}