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:
// omae wa mou shindeiru

#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;

#define ff              first
#define ss              second
#define float           double
#define ll              long long
#define int             long long
#define pb              push_back
#define ppb             pop_back
#define pf              push_front
#define ppf             pop_front
#define mp              make_pair
#define all(v)          v.begin(),v.end()
#define uniq(v)         (v).erase(unique(all(v)),(v).end())
#define endl            "\n"

#define pii             pair<int,int>
#define pll             pair<ll, ll>
#define vi              vector<int>
#define vl              vector<ll>
#define vpii            vector<pii>
#define vpll            vector<pll>
#define vvi             vector<vi>
#define vvl             vector<vl>

#define rep(i,a,b)      for(int i=a;i<b;i++)
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mem1(a)         memset(a,-1,sizeof(a))
#define mem0(a)         memset(a,0,sizeof(a))
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)

#define PI              3.1415926535897932384626433832795
#define eps             1e-9
#define mod             1000000007
#define inf             1e18

mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T, typename T1>T amax(T &a, T1 b) {if (b > a)a = b; return a;}
template<typename T, typename T1>T amin(T &a, T1 b) {if (b < a)a = b; return a;}
//template<typename T> using pbds = tree<T , null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update>;

set<int> s[2];
vi color;
vvi v;

void dfs(int i)
{
    color[i] = 1;
    for (auto x : v[i])
    {
        if (color[x] == 0)
            dfs(x);
        else
            s[color[x] - 1].insert(x);
    }
    color[i] = 2;
}

void dfs2(int i, vi &c)
{
    c[i] = 1;
    for (auto x : v[i])
    {
        if (c[x] == 0)
            dfs2(x, c);
    }
    c[i] = 2;
}



void runtime()
{
    int n, m;
    cin >> n >> m;
    v.clear();
    v.resize(n + 1);
    s[0].clear();
    s[1].clear();
    color.clear();
    color.resize(n+1);

    for(int i=1;i<=m;i++)
    {
        int x, y;
        cin >> x >> y;
        v[x].pb(y);
    }
    dfs(1);
    vi c[2];
    c[0].resize(n + 1);
    c[1].resize(n + 1);
    for (auto x : s[0])
    {
        if (c[0][x] == 0)
            dfs2(x, c[0]);
    }
    for (auto x : s[1])
    {
        if (c[1][x] == 0)
            dfs2(x, c[1]);
    }
    for (int i = 1; i <= n; i++)
    {
        if (!color[i])
        {
            cout << 0 << " ";
        }
        else if(c[0][i])
        {
            cout << -1 << " ";
        }
        else if(c[1][i])
        {
            cout << 2 << " "; 
        }
        else
            cout << 1 << " ";
    }


}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int TESTS = 1; // one input
    cin >> TESTS;
    while (TESTS--) {
        runtime();
        cout << "\n";
    }
    return 0;
}