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:
/*
stream Butter!
eggyHide eggyVengeance
I need U
xiao rerun when
 */
import static java.lang.Math.*;
import static java.lang.System.out;
import java.util.*;
import java.io.*;
import java.math.*;

public class x1547G
{
    static ArrayDeque<Integer>[] edges;
    static ArrayDeque<Integer>[] transpose;
    static final int INF = Integer.MAX_VALUE/2;
    public static void main(String hi[]) throws Exception
    {
        FastScanner infile = new FastScanner();
        int T = infile.nextInt();
        StringBuilder sb = new StringBuilder();
        while(T-->0)
        {
            int N = infile.nextInt();
            int M = infile.nextInt();
            edges = new ArrayDeque[N];
            transpose = new ArrayDeque[N];
            for(int i=0; i < N; i++)
            {
                edges[i] = new ArrayDeque<Integer>();
                transpose[i] = new ArrayDeque<Integer>();
            }
            boolean[] selfloop = new boolean[N];
            for(int aa=0; aa < M; aa++)
            {
                int a = infile.nextInt()-1;
                int b = infile.nextInt()-1;
                edges[a].add(b);
                transpose[b].add(a);
                if(a == b)
                    selfloop[a] = true;
            }
            ArrayList<Integer> order = new ArrayList<Integer>();
            boolean[] seenT = new boolean[N];
            for(int v=0; v < N; v++)
                if(!seenT[v])
                    topsort(v, order, seenT);
            Collections.reverse(order);
            int boof = 0;
            int[] component = new int[N];
            Arrays.fill(component, -1);
            for(int v: order)
                if(component[v] == -1)
                {
                    assignID(v, component, boof);
                    boof++;
                }
            int K = boof;
            int[] size = new int[K];
            for(int v=0; v < N; v++)
            {
                size[component[v]]++;
                if(selfloop[v])
                    size[component[v]]++;
            }
            ArrayDeque<Integer>[] sccEdges = new ArrayDeque[K];
            for(int i=0; i < K; i++)
                sccEdges[i] = new ArrayDeque<Integer>();
            for(int a=0; a < N; a++)
                for(int b: edges[a])
                    if(component[a] != component[b])
                    {
                        //System.out.println(a+" "+b);
                        sccEdges[component[a]].add(component[b]);
                    }
            order = new ArrayList<Integer>();
            boolean[] seen = new boolean[K];
            topsortScc(component[0], order, seen, sccEdges);
            Collections.reverse(order);
            int[] dp = new int[K];
            dp[component[0]] = 1;
            if(size[component[0]] >= 2)
                dp[component[0]] = INF;
            for(int curr: order)
            {
                for(int next: sccEdges[curr])
                {
                    if(size[next] >= 2)
                        dp[next] = INF;
                    else if(dp[curr] == INF)
                        dp[next] = INF;
                    else if(dp[next] < INF)
                    {
                        dp[next] += dp[curr];
                        dp[next] = min(dp[next], 2);
                    }
                }
            }
            for(int v=0; v < N; v++)
            {
                int val = dp[component[v]];
                if(val != INF)
                    sb.append(min(val, 2));
                else
                    sb.append(-1);
                sb.append(" ");
            }
            sb.append("\n");
        }
        System.out.print(sb);
    }
    public static void topsort(int curr, ArrayList<Integer> path, boolean[] seen)
    {
        seen[curr] = true;
        for(int next: edges[curr])
            if(!seen[next])
                topsort(next, path, seen);
        path.add(curr);
    }
    public static void assignID(int curr, int[] comp, int id)
    {
        comp[curr] = id;
        for(int next: transpose[curr])
            if(comp[next] == -1)
                assignID(next, comp, id);
    }
    public static void topsortScc(int curr, ArrayList<Integer> path, boolean[] seen, ArrayDeque<Integer>[] e)
    {
        seen[curr] = true;
        for(int next: e[curr])
            if(!seen[next])
                topsortScc(next, path, seen, e);
        path.add(curr);
    }
    static boolean debug = false;
    public static void print(int[] arr)
    {
        //for debugging only
        for(int x: arr)
            out.print(x+" ");
        out.println();
    }
}
/*
1
4 4
1 2
2 3
1 4
4 3

 */
class FastScanner
{
    //I don't understand how this works lmao
    private int BS = 1 << 16;
    private char NC = (char) 0;
    private byte[] buf = new byte[BS];
    private int bId = 0, size = 0;
    private char c = NC;
    private double cnt = 1;
    private BufferedInputStream in;

    public FastScanner() {
        in = new BufferedInputStream(System.in, BS);
    }

    public FastScanner(String s) {
        try {
            in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
        } catch (Exception e) {
            in = new BufferedInputStream(System.in, BS);
        }
    }

    private char getChar() {
        while (bId == size) {
            try {
                size = in.read(buf);
            } catch (Exception e) {
                return NC;
            }
            if (size == -1) return NC;
            bId = 0;
        }
        return (char) buf[bId++];
    }

    public int nextInt() {
        return (int) nextLong();
    }

    public int[] nextInts(int N) {
        int[] res = new int[N];
        for (int i = 0; i < N; i++) {
            res[i] = (int) nextLong();
        }
        return res;
    }

    public long[] nextLongs(int N) {
        long[] res = new long[N];
        for (int i = 0; i < N; i++) {
            res[i] = nextLong();
        }
        return res;
    }

    public long nextLong() {
        cnt = 1;
        boolean neg = false;
        if (c == NC) c = getChar();
        for (; (c < '0' || c > '9'); c = getChar()) {
            if (c == '-') neg = true;
        }
        long res = 0;
        for (; c >= '0' && c <= '9'; c = getChar()) {
            res = (res << 3) + (res << 1) + c - '0';
            cnt *= 10;
        }
        return neg ? -res : res;
    }

    public double nextDouble() {
        double cur = nextLong();
        return c != '.' ? cur : cur + nextLong() / cnt;
    }

    public double[] nextDoubles(int N) {
        double[] res = new double[N];
        for (int i = 0; i < N; i++) {
            res[i] = nextDouble();
        }
        return res;
    }

    public String next() {
        StringBuilder res = new StringBuilder();
        while (c <= 32) c = getChar();
        while (c > 32) {
            res.append(c);
            c = getChar();
        }
        return res.toString();
    }

    public String nextLine() {
        StringBuilder res = new StringBuilder();
        while (c <= 32) c = getChar();
        while (c != '\n') {
            res.append(c);
            c = getChar();
        }
        return res.toString();
    }

    public boolean hasNext() {
        if (c > 32) return true;
        while (true) {
            c = getChar();
            if (c == NC) return false;
            else if (c > 32) return true;
        }
    }
}