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:
// Don't place your source in a package


import javax.swing.*;
import java.lang.reflect.Array;
import java.text.DecimalFormat;
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;
import java.util.stream.Stream;



// Please name your class Main
public class Main {
    static FastScanner fs=new FastScanner();
    static class FastScanner {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer("");
        public String next() {
            while (!st.hasMoreElements())
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }
        int Int() {
            return Integer.parseInt(next());
        }

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

        String Str(){
            return next();
        }
    }


    public static void main (String[] args) throws java.lang.Exception {
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        //reading /writing file
        //Scanner sc=new Scanner(new File("input.txt"));
        //PrintWriter pr=new PrintWriter("output.txt");

        int T=Int();
        for(int t=0;t<T;t++){
            int n=Int();
            int m=Int();
            int edges[][]=new int[m][2];
            for(int i=0;i<m;i++){
                edges[i][0]=Int()-1;
                edges[i][1]=Int()-1;
            }

            Solution sol=new Solution(out);
            sol.solution(n,edges);
        }
        out.close();

    }

    public static int[] Arr(int n){
        int A[]=new int[n];
        for(int i=0;i<n;i++)A[i]=Int();
        return A;
    }
    public static int Int(){
        return fs.Int();
    }
    public static long Long(){
        return fs.Long();
    }
    public static String Str(){
        return fs.Str();
    }

}








class Solution {
    PrintWriter out;
    int INF = Integer.MAX_VALUE;
    int MOD = 1000000007;

    public Solution(PrintWriter out) {
        this.out = out;
    }


    List<Integer>graph[];
    int seen[];
    public void solution(int n,int edges[][]) {
        graph=new ArrayList[n];
        seen=new int[n];
        Arrays.setAll(graph,e->new ArrayList<>());
        for(int edge[]:edges){
            int u=edge[0],v=edge[1];
            graph[u].add(v);
        }

        seen[0]=1;
        Set<Integer>stack=new HashSet<>();
        stack.add(0);
        dfs(0,stack);

        for(int i:seen){
            out.print(i+" ");
        }
        out.println();
    }

    public void dfs(int root,Set<Integer>stack){
        //System.out.println((root+1)+"  "+Arrays.toString(seen));
        for(int next:graph[root]){
            if(seen[next]==0){//not seen
                seen[next]=1;
                stack.add(next);
                dfs(next,stack);
                stack.remove(next);
            }
            else{
                if(seen[next]==1){
                    if(stack.contains(next)){
                        seen[next]=-1;
                        dfs1(next,-1);
                    }
                    else{
                        seen[next]=2;
                        dfs1(next,2);
                    }
                }
                else if(seen[next]==2){
                    if(stack.contains(next)){
                        seen[next]=-1;
                        dfs1(next,-1);
                    }
                }
            }
        }

    }

    public void dfs1(int root,int color){//color infinite
        for(int next:graph[root]){
            if(seen[next]!=color){
                if(color==2){
                    if(seen[next]!=-1){
                        seen[next]=color;
                        dfs1(next,color);
                    }
                }
                else{
                    seen[next]=color;
                    dfs1(next,color);
                }

            }
        }
    }



}