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:
//Created by Aminul on 7/10/2021.

import java.io.*;
import java.util.*;

public class G {
    public static void main(String[] args) throws Exception {
        new Thread(null ,new Runnable(){
            public void run(){
                try{solveIt();} catch(Exception e){e.printStackTrace(); System.exit(1);}
            }
        },"Main",1<<28).start();
    }
    
    public static void solveIt() throws Exception {
        InputReader in = new InputReader(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int test = in.nextInt();
        for (int t = 1; t <= test; t++) {
            int n = in.nextInt();
            int m = in.nextInt();
            boolean[] selfLoop = new boolean[n];
            List<Integer>[] g = genList(n);
            for (int i = 0; i < m; i++) {
                int u = in.nextInt() - 1, v = in.nextInt() - 1;
                if (u != v) {
                    g[u].add(v);
                } else {
                    selfLoop[u] = true;
                }
            }

            SCCTarjan scc = new SCCTarjan();
            List<List<Integer>> comps = scc.scc(g);
            List<Integer>[] dag = scc.sccToDAG(g, comps);
            int[] compId = scc.compId;

            long[] res = solve(n, 0, compId, dag, comps, selfLoop);

            for (int i = 0; i < n; i++) {
                int id = compId[i];
                if (res[id] <= 1) {
                    pw.print(res[id] + " ");
                } else {
                    pw.print("2 ");
                }
            }
            pw.println();
        }

        pw.close();
    }

    static void dfs(int node, List<Integer>[] g, boolean[] vis) {
        vis[node] = true;
        for (int v : g[node]) {
            if (!vis[v]) {
                dfs(v, g, vis);
            }
        }
    }

    static long[] solve(int N, int root, int[] compId, List<Integer>[] g,
                        List<List<Integer>> comps, boolean[] selfLoop) {

        root = compId[root];
        int n = g.length;
        int[] inDegree = new int[n];
        long[] res = new long[n];

        boolean[] vis = new boolean[n];
        dfs(root, g, vis);

        res[root] = 1;

        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                continue;
            }
            for (int j : g[i]) {
                inDegree[j]++;
            }
            if (comps.get(i).size() > 1) {
                res[i] = -1;
            }
        }

        for (int i = 0; i < N; i++) {
            if (vis[compId[i]] && selfLoop[i]) {
                res[compId[i]] = -1;
            }
        }

        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int v : g[node]) {
                if (res[v] != -1) {
                    if (res[node] == -1) {
                        res[v] = -1;
                    } else if (res[v] < 2) {
                        res[v] += res[node];
                    }
                }
                inDegree[v]--;
                if (inDegree[v] == 0) {
                    queue.add(v);
                }
            }
        }
        return res;
    }

    static <T> List<T>[] genList(int n) {
        List<T> list[] = new List[n];
        for (int i = 0; i < n; i++) list[i] = new ArrayList<T>();
        return list;
    }

    static class SCCTarjan { //0-based indexed
        List<Integer>[] graph;
        boolean[] visited;
        Stack<Integer> stack;
        int time;
        int[] lowlink;
        List<List<Integer>> components;
        int[] compId;

        public List<List<Integer>> scc(List<Integer>[] graph) {
            int n = graph.length;
            this.graph = graph;
            visited = new boolean[n];
            stack = new Stack<>();
            time = 0;
            lowlink = new int[n];
            components = new ArrayList<>();

            for (int u = 0; u < n; u++)
                if (!visited[u])
                    dfs(u);

            return components;
        }

        void dfs(int u) {
            lowlink[u] = time++;
            visited[u] = true;
            stack.add(u);
            boolean isComponentRoot = true;

            for (int v : graph[u]) {
                if (!visited[v])
                    dfs(v);
                if (lowlink[u] > lowlink[v]) {
                    lowlink[u] = lowlink[v];
                    isComponentRoot = false;
                }
            }

            if (isComponentRoot) {
                List<Integer> component = new ArrayList<>();
                while (true) {
                    int x = stack.pop();
                    component.add(x);
                    lowlink[x] = Integer.MAX_VALUE;
                    if (x == u)
                        break;
                }
                components.add(component);
            }
        }

        public List<Integer>[] sccToDAG() {
            return sccToDAG(graph, components);
        }

        public List<Integer>[] sccToDAG(List<Integer>[] graph, List<List<Integer>> components) {
            compId = new int[graph.length];
            for (int i = 0; i < components.size(); i++)
                for (int u : components.get(i))
                    compId[u] = i;
            List<Integer>[] g = new List[components.size()];
            for (int i = 0; i < components.size(); ++i) g[i] = new ArrayList<>();
            for (int u = 0; u < graph.length; u++)
                for (int v : graph[u])
                    if (compId[u] != compId[v])
                        g[compId[u]].add(compId[v]);
            return g;
        }
    }

    static void debug(Object... obj) {
        System.err.println(Arrays.deepToString(obj));
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        public String next() throws Exception {
            while (tokenizer == null || !tokenizer.hasMoreTokens())
                tokenizer = new StringTokenizer(reader.readLine());
            return tokenizer.nextToken();
        }

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