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 JAVA):

Solution:
// package codeforce.cf731;

import java.io.PrintWriter;
import java.util.*;
//https://codeforces.com/contest/1547/problem/G
public class G {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int t = sc.nextInt();
//        int t = 1;
        for (int i = 0; i < t; i++) {
            solve(sc, pw);
        }
        pw.close();
    }
    static class Edge{
        int from, to;
        public Edge(int from, int to) {
            this.from = from;
            this.to = to;
        }
    }
    static class Node{
        List<Node> nxt = new ArrayList<>();
        boolean isReachable = false;
        int visitedTime = 0;
        boolean isLooped = true;
        int idx;
        public Node(int idx) {
            this.idx = idx;
        }
    }
    static void solve(Scanner in, PrintWriter out){
        int n = in.nextInt(), m = in.nextInt();
        Edge[] edges = new Edge[m];
        Node[] nodes = new Node[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = new Node(i);
        }
        int[] pars = new int[n];
        for (int i = 0; i < m; i++) {
            edges[i] = new Edge(in.nextInt() - 1, in.nextInt() - 1);
            nodes[edges[i].from].nxt.add(nodes[edges[i].to]);
        }
        bfs(nodes, n);
        for (int i = 0; i < m; i++) {
            if (nodes[edges[i].from].isReachable) pars[nodes[edges[i].to].idx]++;
        }
        topo(nodes, n, pars);
        dfs(nodes[0]);
        for (int i = 0; i < n; i++) {
            if (!nodes[i].isReachable){
                out.print(0+" ");
                continue;
            }
            if (nodes[i].isLooped){
                out.print(-1+" ");
            }else{
                out.print(nodes[i].visitedTime+" ");
            }
        }
        out.println();
    }
    static void dfs(Node node){
        if (node.isLooped || node.visitedTime >= 2) return;
        node.visitedTime++;
        for(Node nxt : node.nxt) dfs(nxt);
    }
    static void bfs(Node[] nodes, int n){
        LinkedList<Node> q = new LinkedList<>();
        q.add(nodes[0]);
        while (!q.isEmpty()){
            Node get = q.poll();
            if (get.isReachable) continue;
            get.isReachable = true;
            for(Node node : get.nxt) q.add(node);
        }
    }
    static void topo(Node[] nodes, int n, int[] pars){
        LinkedList<Node> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (pars[i] == 0 && nodes[i].isReachable) q.add(nodes[i]);
        }
        while (!q.isEmpty()){
            Node node = q.poll();
            node.isLooped = false;
            for(Node nxt : node.nxt){
                pars[nxt.idx]--;
                if (pars[nxt.idx] == 0) q.add(nxt);
            }
        }

    }


    // Use this instead of Arrays.sort() on an array of ints. Arrays.sort() is n^2
    // worst case since it uses a version of quicksort. Although this would never
    // actually show up in the real world, in codeforces, people can hack, so
    // this is needed.
    static void ruffleSort(int[] a) {
        //ruffle
        int n=a.length;
        Random r=new Random();
        for (int i=0; i<a.length; i++) {
            int oi=r.nextInt(n), temp=a[i];
            a[i]=a[oi];
            a[oi]=temp;
        }

        //then sort
        Arrays.sort(a);
    }

}