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 com.company;


//ankit singh

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
public class Main {

    static ArrayList<Integer> graph[];
     static   boolean cyc[],vis[];
     static int in[],pos[];
    public static void main(String[] args) {
        FastReader input=new FastReader();
        PrintWriter out=new PrintWriter(System.out);
        int t=input.nextInt();
        while (t-->0){
            int n=input.nextInt();
            int m=input.nextInt();
            graph=new ArrayList[n+1];
            cyc=new boolean[n+1];
            vis=new boolean[n+1];
            for (int i = 0; i <=n ; i++) {
                graph[i]=new ArrayList<>();
            }
            while (m-->0){
                int x=input.nextInt();
                int y=input.nextInt();
                graph[x].add(y);
            }
            in=new int[n+1];
            pos= new int[n + 1];

            dfs(1,0);
//            for (int i = 1; i <=n ; i++) {
//                System.out.println(i+" "+cyc[i]);
//            }

            for (int i = 1; i <=n ; i++) {
                if (cyc[i])
                 dfs2(i);
            }
            //vis[i]=true currently for all cycle int
            for (int i = 1; i <=n ; i++) {
                if (!vis[i] && pos[i]>1)
                    dfs3(i);
            }
            for (int i = 1; i <=n ; i++) {
              if (cyc[i]){
                  out.print("-1 ");
                  continue;
              }
              if (pos[i]>1){
                  out.print("2 ");
              }else if (pos[i]==1){
                 out.print("1 ");
              }else {
                 out.print("0 ");
              }
            }
            out.println();



        }
        out.flush();
        out.close();


    }

    private static void dfs3(int r) {


        vis[r]=true;

        for (int c:graph[r]) {
            if (vis[c]) continue;
            pos[c]=2;
            dfs3(c);
        }
    }

    private static void dfs2(int r) {
        if (vis[r]) return;

        vis[r]=true;
        cyc[r]=true;
        for (int c:graph[r]) {
            if (cyc[c]) continue;
            dfs2(c);
        }

    }

    private static int dfs(int r,int t) {
        int max=Integer.MAX_VALUE;
        in[r]=t;
        t++;
        vis[r]=true;
        pos[r]++;


        for (int c:graph[r]) {
            if (vis[c]){
                max=Math.min(max,in[c]);
                cyc[r]=true;
                continue;
            }
            if (pos[c] >0 ){
                pos[c]++;
                continue;
            }

           int x=  dfs(c,t);
            if (x!=Integer.MAX_VALUE){
                cyc[r]=true;
                max=Math.min(max,x);
            }
        }
        if (max==in[r]) max=Integer.MAX_VALUE;
        vis[r]=false;
        return max;
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

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

        String next()
        {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

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

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine()
        {
            String str = "";
            try {
                str = br.readLine();
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

}