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:
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String args[]) {
        new Main().run();
    }

    FastReader in = new FastReader();
    PrintWriter out = new PrintWriter(System.out);

    void run() {
        for(int q=ni();q>0;q--){
            work();
        }
        out.flush();
    }

    long mod = 1000000007;
    long gcd(long a, long b) {
        return a == 0 ? b : gcd(b % a, a);
    }
    long inf = Long.MAX_VALUE / 3;
    ArrayList<Integer>[] graph;
    int[] ret;
    int[] color;
    int[] label;
    int[] pre;
    int cur=1;
    void work() {
        int n=ni(),m=ni();
        graph=ng(n,m);
        ret=new int[n];
        color=new int[n];
        label=new int[n];
        pre=new int[n];
        Arrays.fill(pre,99999999);
        dfs1(0);
        LinkedList<Integer> q1=new LinkedList<>();
        for(int i=0;i<n;i++){
            if(ret[i]==2){
                q1.add(i);
            }
        }
        boolean[] vis=new boolean[n];
        while(q1.size()>0){
            int node=q1.poll();
            ret[node]=2;
            for(int nn:graph[node]){
                if(!vis[nn]){
                    vis[nn]=true;
                    q1.add(nn);
                }
            }
        }
        color=new int[n];
        dfs2(0);
        vis=new boolean[n];
        for(int i=0;i<n;i++){
            if(ret[i]==-1){
                q1.add(i);
            }
        }
        while(q1.size()>0){
            int node=q1.poll();
            ret[node]=-1;
            for(int nn:graph[node]){
                if(!vis[nn]){
                    vis[nn]=true;
                    q1.add(nn);
                }
            }
        }
        for(int r:ret){
            out.print(r+" ");
        }
        out.println();
    }

    private void dfs2(int node) {
        if(color[node]==2){
            return;
        }
        color[node]=1;
        label[node]=cur++;
        for(int nn:graph[node]){
            if(color[nn]==1){
                pre[node]=Math.min(pre[node],label[nn]);
            }else if(color[nn]==0){
                dfs2(nn);
                pre[node]=Math.min(pre[node],pre[nn]);
            }
        }
        if(pre[node]<=label[node]){
            ret[node]=-1;
        }
        color[node]=2;
    }

    private void dfs1(int node) {
        ret[node]=1;
        if(color[node]>0){
            ret[node]=2;
            return;
        }
        color[node]=1;
        for(int nn:graph[node]){
            dfs1(nn);
        }
    }


    private ArrayList<long[]>[] ngw(int n, int m) {
        ArrayList<long[]>[] graph = (ArrayList<long[]>[]) new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 1; i <= m; i++) {
            long s = in.nextLong() - 1, e = in.nextLong() - 1, w = in.nextLong();
            graph[(int) s].add(new long[]{e, w});
            graph[(int) e].add(new long[]{s, w});
        }
        return graph;
    }

    private ArrayList<Integer>[] ng(int n, int m) {
        ArrayList<Integer>[] graph = (ArrayList<Integer>[]) new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 1; i <= m; i++) {
            int s = in.nextInt() - 1, e = in.nextInt() - 1;
            graph[s].add(e);
//            graph[e].add(s);
        }
        return graph;
    }

    private int ni() {
        return in.nextInt();
    }

    private long nl() {
        return in.nextLong();
    }

    private String ns() {
        return in.next();
    }

    private long[] na(int n) {
        long[] A = new long[n];
        for (int i = 0; i < n; i++) {
            A[i] = in.nextLong();
        }
        return A;
    }

    private int[] nia(int n) {
        int[] A = new int[n];
        for (int i = 0; i < n; i++) {
            A[i] = in.nextInt();
        }
        return A;
    }
}

class FastReader {
    BufferedReader br;
    StringTokenizer st;

    public FastReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }


    public String next() {
        while (st == null || !st.hasMoreElements())//回车，空行情况
        {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public long nextLong() {
        return Long.parseLong(next());
    }
}