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 int64 = long long;
using ar2 = array<int,2>;
constexpr int MAXN = 5+400000;

namespace kos {
int my_scc[MAXN], sccno = 0, n = -1; // node to scc, sccno = # of scc
vector<int> g[MAXN], rg[MAXN];
stack<int> ts;
bool vis[MAXN];
void dfs(int u, bool revg) {
  vis[u] = true;
  if (revg) my_scc[u] = sccno;
  const auto& gw = (revg ? rg : g);
  for (int v : gw[u]) if (!vis[v]) dfs(v,revg);
  if (!revg) ts.push(u);
}
void solve() {
  fill(vis, vis+n, false);
  for (int u = 0; u < n; ++u) {
    if (!vis[u]) dfs(u,false);
    for (int v : g[u]) rg[v].push_back(u);
  }
  fill(vis, vis+n, false);
  sccno = 0;
  while (!ts.empty()) {
    int u = ts.top();ts.pop();
    if (!vis[u]) dfs(u,true), sccno++;
  }
}}

vector<int> g2[MAXN];
bitset<MAXN> visited1;
bool loop[MAXN], path[MAXN];

void dfs1(int u) {
  visited1[u] = true;
  for (int v : g2[u]) {
    if (!visited1[v]) {
      dfs1(v);
    } else {
      path[v] = true;
    }
  }
}

void dfs2(int u, bool arr[]) {
  arr[u] = true;
  for (int v : g2[u]) {
    if (!arr[v]) {
      dfs2(v, arr);
    }
  }
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
  int tc; cin >> tc;
  while (tc--) {
    using kos::n;
    using kos::g;
    using kos::rg;
    int m; cin >> n >> m;
    for (int i = 0; i < n; ++i) {
      g[i].clear();
      g2[i].clear();
      rg[i].clear();
      loop[i] = path[i] = visited1[i] = false;
    }
    while (m--) {
      int a,b; cin >> a >> b; --a; --b;
      g[a].push_back(b);
    }
    kos::solve();
    for (int u = 0; u < n; ++u) {
      for (int v : g[u]) {
        assert(kos::my_scc[u] <= kos::my_scc[v]);
        g2[kos::my_scc[u]].push_back(kos::my_scc[v]);
        if (kos::my_scc[u] == kos::my_scc[v]) {
          loop[kos::my_scc[u]] = true;
        }
      }
    }
    dfs1(kos::my_scc[0]);
    for (int i = kos::sccno-1; i >= kos::my_scc[0]; --i) {
      if (loop[i]) {
        dfs2(i, loop);
      }
      if (path[i]) {
        dfs2(i, path);
      }
    }
    for (int i = 0; i < n; ++i) {
      if (i > 0) cout << ' ';
      if (!visited1[kos::my_scc[i]]) {
        cout << 0;
      } else if (loop[kos::my_scc[i]]) {
        cout << -1;
      } else if (path[kos::my_scc[i]]) {
        cout << 2;
      } else {
        cout << 1;
      }
    }
    cout << '\n';
  }
  return 0;
}