Problem: You are given a directed graph with n vertices and m directed edges without self-loops or multiple edges.

Let's denote the k-coloring of a digraph as following: you color each edge in one of k colors. The k-coloring is good if and only if there no cycle formed by edges of same color.

Find a good k-coloring of given digraph with minimum possible k.

Input

The first line contains two integers n and m (2 ≤ n ≤ 5000, 1 ≤ m ≤ 5000) — the number of vertices and edges in the digraph, respectively.

Next m lines contain description of edges — one per line. Each edge is a pair of integers u and v (1 ≤ u, v ≤ n, u ≠ v) — there is directed edge from u to v in the graph.

It is guaranteed that each ordered pair (u, v) appears in the list of edges at most once.

Output

In the first line print single integer k — the number of used colors in a good k-coloring of given graph.

In the second line print m integers c_1, c_2, ..., c_m (1 ≤ c_i ≤ k), where c_i is a color of the i-th edge (in order as they are given in the input).

If there are multiple answers print any of them (you still have to minimize k).

Examples

Input


4 5
1 2
1 3
3 4
2 4
1 4


Output


1
1 1 1 1 1 


Input


3 3
1 2
2 3
3 1


Output


2
1 1 2 

Solution (in JAVA):

Solution:


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

public class D1217 {

    public static void main(String[] args) throws IOException {
        BufferedReader inp = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s1 = inp.readLine().split(" ");
        int vertices = Integer.parseInt(s1[0]);
        int edges = Integer.parseInt(s1[1]);
        GraphD1217 graph = new GraphD1217(vertices);
        for(int i=0;i<edges;i++){
            String[] s2 = inp.readLine().split(" ");
            graph.addEdge(Integer.parseInt(s2[0]),Integer.parseInt(s2[1]),i);
        }
        graph.DFS(edges);
    }
}
class GraphD1217{
    class Pair{
        int a, b;
        Pair(int a,int b){
            this.a = a;
            this.b = b;
        }
    }
    int vertices;
    ArrayList<Pair> edge[];
    static Map<Integer,Integer> parent;
    static Map<Integer,Integer> color;
    static boolean cycle;
    static boolean[] visited;
    GraphD1217(int vertices){
        cycle = false;
        visited = new boolean[vertices+1];
        this.vertices = vertices;
        edge = new ArrayList[vertices+1];
        parent = new HashMap<>();
        color = new HashMap<>();
        for(int i=0;i<=vertices;i++){
            edge[i] = new ArrayList<>();
        }

    }
    void addEdge(int a,int b,int c){
        edge[a].add(new Pair(b,c));
    }
    void DFS(int edges){
        Set<Integer> greySet = new HashSet<>();
        parent.put(1,0);
        for(int i=1;i<=vertices;i++){
            if(!visited[i]){
                DFSutil(i,greySet,visited);
            }
        }
       
        if(cycle){
            System.out.println(2);
        }
        else{
            System.out.println(1);
        }
        for(int i=0;i<edges;i++){
            if(color.containsKey(i)){
                System.out.print(2+" ");
            }
            else{
                System.out.print(1+" ");
            }
        }
    }

    private void DFSutil(int v, Set<Integer> greySet, boolean[] visited) {
        ArrayList<Integer> ret = new ArrayList<>();
        visited[v] = true;
        greySet.add(v);
        Iterator<Pair> iterator = edge[v].listIterator();
        while (iterator.hasNext()){
            Pair node = iterator.next();
            int n = node.a;
            if(!visited[n] ){
                parent.put(n,v);
                DFSutil(n,greySet,visited);
            }
            else {
                if(greySet.contains(n)){
                    color.put(node.b,1);
                    cycle = true;
                }
            }
        }
        greySet.remove(v);
    }

}