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>
#define ll long long
#define fi first
#define se second
using namespace std;
const int inf = 2e9, N = 1e6 + 1;
vector<bool> vis, vis2, vis3, has, has2;
vector<int> ord, idx, lf, ans;
vector<vector<int>> g, p, elm, g2;
void dfs(int u){
    vis[u] = 1;
    for (int i : g[u]){
        if (!vis[i]) dfs(i);
    }
    ord.push_back(u);
}
int t = 0;
void reduce(){
    for (int i : ord){
        if (vis2[i]) continue;
        queue<int> q;
        q.push(i);
        vis2[i] = 1;
        while (!q.empty()){
            int u = q.front();
            q.pop();
            idx[u] = t;
            elm[t].push_back(u);
            for (int j : g2[u]){
                if (!vis2[j]){
                    vis2[j] = 1;
                    q.push(j);
                }
            }
            //cout << vis2[1] << ' ' << t << ' ' << u << '\n';
        }
        if (elm[t].size() > 1) has2[t] = 1;
        else if (has[i]) has2[t] = 1;
        t++;
    }
}
void build(){
    for (int i = 0; i < t; i++){
        int cnt = 0;
        for (int j : elm[i]){
            for (int k : g[j]){
                int u = idx[k];
                if (i == u) continue;
                cnt++;
                p[u].push_back(i);
                //cout << i << ' ' << u << '\n';
            }
        }
        if (!cnt) lf.push_back(i);
    }
}
void dfs2(int u){
    //cout << u << '\n';
    vis3[u] = 1;
    int cnt = 0;
    if (u == idx[0]){
        ans[u] = has2[u] ? 3 : 1;
    }
    else ans[u] = 0;
    for (int i : p[u]){
        if (!vis3[i]) dfs2(i);
        ans[u] = max(ans[u], ans[i]);
        if (ans[i] != 0) cnt++;
    }
    if (cnt > 1) ans[u] = max(ans[u], 2);
    if (ans[u] and has2[u]) ans[u] = 3;
}
void init(int n){
    t = 0;
    vis.resize(n), vis2.resize(n), vis3.resize(n), has.resize(n), has2.resize(n);
    ord.clear(), lf.clear();
    idx.resize(n), ans.resize(n);
    g.resize(n), p.resize(n), g2.resize(n), elm.resize(n);
    for (int i = 0; i < n; i++) vis[i] = 0;
    for (int i = 0; i < n; i++) vis2[i] = 0;
    for (int i = 0; i < n; i++) vis3[i] = 0;
    for (int i = 0; i < n; i++) has[i] = 0;
    for (int i = 0; i < n; i++) has2[i] = 0;
    for (auto &i : g) i.clear();
    for (auto &i : p) i.clear();
    for (auto &i : g2) i.clear();
    for (auto &i : elm) i.clear();
}
void solve(){
    int n, m;
    cin >> n >> m;
    init(n);
    for (int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        u--, v--;
        g[u].push_back(v);
        g2[v].push_back(u);
        if (u == v) has[u] = 1;
    }
    for (int i = 0; i < n; i++) if (!vis[i]) dfs(i);
    reverse(ord.begin(), ord.end());
    reduce();
    build();
    for (int i : lf) dfs2(i);
    //cout << "ya\n";
    //cout << has2[2] << ' ' << has2[3] << '\n';
    //cout << idx[0] << idx[1] << idx[2] << '\n';
    for (int i = 0; i < n; i++) cout << (ans[idx[i]] == 3 ? -1 : ans[idx[i]]) << ' ';
    cout << '\n';
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while(t--) solve();
}