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;
using lli = long long int;
using ull = unsigned long long;
using uli = unsigned long long int;
using ld = long double;
using db = double;

using ii = pair<int, int>;
using iii = pair<ii, int>;
using pl = pair<ll, ll>;
using pd = pair<ld,ld>;
using si = pair<int, string>;

using ti = tuple<int, int, int>;
using tll = tuple<ll, ll, ll>;
using tld = tuple<ld, ld, ld>;

using vi = vector<int>;
using vd = vector<ld>;
using vl = vector<ll>;
using vii = vector<ii>;
using vpl = vector<pl>;
using vc = vector<char>;
using vs = vector<string>;

using mii = unordered_map<int,int>;
using mll = map<ll,ll>;
using mci = map<char,int>;
using msi = map<string,int>;
using mss = map<string, string>;

#define mp make_pair
#define pb push_back
#define pf push_front
#define pp pop_back
#define ppf pop_front
#define ff first
#define ss second
#define lb lower_bound // pointer to the first element which has a value not less than val.
#define ub upper_bound // pointer to the first element that is greater than val.
#define sz(v) ((int)v.size())
#define all(x) (x).begin() , (x).end()
#define mt make_tuple // get<0>(a); tie(a, b, w)=e;
#define Queue priority_queue<int,vector<int>,greater<int>>
#define PQ priority_queue<ii, vector<ii>, greater<ii>>
#define np(p, n) next_permutation(p, p+n)
#define setp(x) cout<<setprecision(x)<<fixed

#define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define F0R(i,a) for(int i=0; i<(a); i++)
#define FOR(i,a,b) for(int i=(a); i<=(b); i++)
#define R0F(i,a) for(int i=(a)-1; i>=0; i--)
#define ROF(i,a,b) for(int i=(b); i>=a; i--)
#define trav(a,x) for (auto& a: x)

#define parse(A, n) for ( ll K = 0; K < n; K++) { cin >> A[K]; }
#define process(A, n) for( ll K = 1; K <= n; K++) { cin >> A[K]; }
#define out(A, n) for ( ll K = 0; K < n; K++) { cout <<(K!=0?" ":"")<<A[K]; }
#define show(x) { bool first=true; for(auto& a:x) { if(first) { first=false; } else { cout<<" "; } cout<<a; } cout<<'\n'; }
#define initialize(memo) memset(memo, -1, sizeof memo);
#define print(k) printf("%.2lf\n", k) // setprecision(3)

int primes[101];
const int N=1000024;
const int M = 30024;
const int inf = 1e9;
const int MAX = 2e5+5;
const int MOD = 1e9+7;
const double EPS = 1e-9;
const double PI = 3.14159265358979323846;
const long long INF = 1e18;
const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0}; //East, West, South, North
const int dr[8] = {1,1,0,-1,-1,-1, 0, 1}, dc[8] = {0,1,1, 1, 0,-1,-1,-1};  // S,SE,E,NE,N,NW,W,SW
enum state {unvisited, visited, explored};

set<char> vowel={'A', 'O', 'Y', 'E', 'U', 'I','a','o','y','e','u','i'};

string to_binary(ll x) { return bitset<64>(x).to_string(); } // Decimal to Binary
ld dist(ld x, ld y, ld a, ld b)    { return sqrt((x-a)*(x-a) + (y-b)*(y-b)); } // hypot(x - a, y - b);
ll gcd(ll a , ll b){ return b ? gcd(b , a % b) : a ;}
ll lcm(ll a , ll b){ return (a * b) / gcd(a , b);}
ll fact(long long  n) {return n > 1?(n * fact(n-1)):1;}
void prime() {  for (int k = 0; k<101; k++){ primes[k] = 1; } primes[1] = 0;
                for (int k = 2; k<101; k++){ if (primes[k]){
                for (int j = 2*k; j<101; j+=k){ primes[j] = 0; }}} }
void IO() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

class UnionFind {
private: vi parents, sizes;
public:
    UnionFind(int N) { sizes.assign(N, 1);
        parents.assign(N, 0); for(int i=0;i<N;i++) parents[i]=i; }
    int findSet(int i) { return (i==parents[i])?i:(parents[i]=findSet(parents[i])); }
    bool isSameSet(int i, int j) { return findSet(i)==findSet(j); }
    void UnionSet(int i, int j) {
        if(!isSameSet(i, j)) {
            int x=findSet(i), y=findSet(j);
            if(sizes[x]<sizes[y]) swap(x, y);
            sizes[x]+=sizes[y]; parents[y]=x;
} } };

class SegmentTree {
private: vi st, A;
    int n;
    int left (int p) { return p << 1; }
    int right(int p) { return (p << 1) + 1; }
    void build(int p, int L, int R) {
        if (L == R) st[p] = L;
        else {
            build(left(p) , L , (L + R) / 2);
            build(right(p), (L + R) / 2 + 1, R );
            int p1 = st[left(p)], p2 = st[right(p)];
            st[p] = (A[p1] <= A[p2]) ? p1 : p2;
    } }
    int rmq(int p, int L, int R, int i, int j) {
    if (i > R || j < L) return -1;
    if (L >= i && R <= j) return st[p];
    int p1 = rmq(left(p) , L , (L+R) / 2, i, j);
    int p2 = rmq(right(p), (L+R) / 2 + 1, R , i, j);
    if (p1 == -1) return p2;
    if (p2 == -1) return p1;
    return (A[p1] <= A[p2]) ? p1 : p2;
}
public:
    SegmentTree(const vi &_A) {
        A = _A; n = (int)A.size();
        st.assign(4 * n, 0);
        build(1, 0, n - 1); }
    int rmq(int i, int j) { return rmq(1, 0, n - 1, i, j); }
};

/** |||||||||||||||||||||||||||||||| SOLUTION |||||||||||||||||||||||||||||||| **/

int n, m; vi topo; int timer; vi S; int ans[N];
vi adj[N]; vector<bool>vis; vi low, tin;
vi dis;
void dfs(int i)
{
    vis[i]=true;
    for(auto u:adj[i])
        if(!vis[u]) dfs(u);
}

void topological(int v)
{
    vis[v]=true;
    for(auto u:adj[v])
        if(!vis[u]) topological(u);
    topo.pb(v);
}

void SCC(int v)
{
    tin[v]=low[v]=timer++;
    vis[v]=true; S.pb(v);
    for(auto u:adj[v])
    {
        if(tin[u]==-1) SCC(u);
        if(vis[u]) low[v]=min(low[v], low[u]);
    }
    if(tin[v]==low[v])
    {
        vi fail;
        while(1) {
            int u=S.back(); S.pp(); vis[u]=false;
            fail.pb(u); if(u==v) break;
        }
        if(sz(fail)>1) {
            while(!fail.empty()) {
                int u=fail.back(); ans[u]=-1; fail.pp();

            }
        }
    }
}
void path(int v, bool c)
{
    for(auto u:adj[v]) {
        dis[u]+=dis[v];
        if(c) ans[u]=-1;
    }
}

int32_t main()
{

    FAST; IO();
    int t; cin>>t;
    while(t--)
    {
        cin>>n>>m;  dis.assign(n+1, 0); dis[1]=1; S.clear();
        memset(ans, 0, sizeof(ans)); ans[1]=1;
        for(int l=0;l<=n;l++) adj[l].clear();
        for(int l=0;l<m;l++) {
            int a, b; cin>>a>>b;
            adj[a].pb(b); if(a==b) ans[a]=-1;
        }
        timer=0;
        tin.assign(n+1, -1); low.assign(n+1, -1); vis.assign(n+1, false);
        for(int l=1;l<=n;l++)
            if(tin[l]==-1) SCC(l);
        vis.assign(n+1, false); topo.clear(); dfs(1);
        for(int l=1;l<=n;l++) if(!vis[l]) ans[l]=-2;
        vis.assign(n+1, false);
        for(int l=1;l<=n;l++)
            if(vis[l]==false) topological(l);
        reverse(all(topo)); vis.assign(n+1, false);
        for(auto u:topo) {
            if(ans[u]==-2) continue;
            path(u, (ans[u]==-1?true:false));
        }
        for(int l=1;l<=n;l++) {
            if(ans[l]==-2||ans[l]==-1) continue;
            ans[l]=(dis[l]==1?1:2);
        }
        for(int l=1;l<=n;l++)
            cout<<(ans[l]!=-2?ans[l]:0)<<" "; cout<<'\n';
    }
    return 0;

}

/* Stuff you should look for :
	* int overflow, array bounds.
	* special cases (n=1?).
	* Observe The Constraints.
	* do smth instead of nothing and stay organized.
	* Reformulate The Problem Into Something More Theoretical.
	* Use flush operator when having TLE.
	* WRITE STUFF DOWN.
	* DON'T GET STUCK ON ONE APPROACH.
   Think of:
    * Brute force, Greedy(High->Low), Dynamic Programming, Divide and Conquer.
    * BFS, DFS, Flood Fill, Topological Sort, Bipartite Check, Articulation Points, SCC.
    * Minimum, Maximum Spanning Tree, SSSP, All-Pairs Shortest Paths, Network Flow.
    * Disjoint Set Union, Segment tree, Math, Two Pointers, Strings.
   Motivation :
    * Change Your Approach.
    * Don't Spend Too Much Time On The Problem: Move On!
    * If You Don't Fight You Cannot Win.
*/