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.lang.*;
import java.util.*;
import java.io.*;

public class Main {
    void solve() {
        int n=ni(),m=ni();
        g=new ArrayList[n+1];
        for(int i=1;i<=n;i++) g[i]=new ArrayList<>();
        Node p[]=new Node[m+1];
        for(int i=1;i<=m;i++){
            int u=ni(),v=ni();
            g[u].add(new Node(v,i));
            p[i]=new Node(u,v);
        }
        color=new int[m+1];
        vis=new int[n+1];
        Arrays.fill(color,-1);
        cycle=false;
        for(int i=1;i<=n;i++){
            if(vis[i]==0) dfs(i);
        }
        if(!cycle){
            pw.println("1");
            for(int i=1;i<=m;i++) pw.print("1 ");
            pw.println("");
            return;
        }
        pw.println("2");
        for(int i=1;i<=m;i++){
            if(p[i].v<p[i].id) pw.print("1 ");
            else pw.print("2 ");
        }

    }
    int color[];
    ArrayList<Node> g[];
    int vis[];
    boolean cycle;
    void dfs(int v){
        vis[v]=1;
        for(Node p : g[v]){
            if(vis[p.v]==0){
                dfs(p.v);
            }else if(vis[p.v]==1){
                cycle=true;
            }
        }
        vis[v]=2;
    }


    class Node {
        int v;
        int id;
        public Node(int v,int id){
            this.v=v;
            this.id=id;
        }
    }

    long M = (long)1e9+7;
    // END
    PrintWriter pw;
    StringTokenizer st;
    BufferedReader br;

    void run() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        pw = new PrintWriter(System.out);
        long s = System.currentTimeMillis();
        solve();
        pw.flush();
    }
    public static void main(String[] args) throws Exception {
        new Main().run();
    }

    String ns() {
        while (st == null || !st.hasMoreElements()) {

            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    String nextLine() throws Exception {
        String str = "";
        try {
            str = br.readLine();
        } catch (IOException e) {
            throw new Exception(e.toString());
        }
        return str;
    }

    int ni() {
        return Integer.parseInt(ns());
    }

    long nl() {
        return Long.parseLong(ns());
    }

    double nd() {
        return Double.parseDouble(ns());
    }
}