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 D
{
    PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer tok;

    public void go() throws IOException
    {
        ntok();
        int n = ipar();
        int m = ipar();
        Vertex[] vertices = new Vertex[n];
        for (int i = 0; i < n; i++)
        {
            vertices[i] = new Vertex();
        }
        int[][] edges = new int[m][2];
        for (int i = 0; i < m; i++)
        {
            ntok();
            edges[i][0] = ipar()-1;
            edges[i][1] = ipar()-1;
            vertices[edges[i][0]].others.add(vertices[edges[i][1]]);
        }
        boolean cycle = false;
        for (Vertex v : vertices)
        {
            if (!v.finished)
            {
                cycle |= dfs(v);
            }
        }
        if (cycle)
        {
            out.println(2);
            for (int i = 0; i < m; i++)
            {
                if (i != 0)
                {
                    out.print(" ");
                }
                if (edges[i][0] < edges[i][1])
                {
                    out.print(1);
                }
                else
                {
                    out.print(2);
                }
            }
        }
        else
        {
            out.println(1);
            for (int i = 0; i < m; i++)
            {
                if (i != 0)
                {
                    out.print(" ");
                }
                out.print(1);
            }
        }
        out.println();

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

    public boolean dfs(Vertex curr)
    {
        if (curr.finished)
        {
            return false;
        }
        if (curr.started)
        {
            return true;
        }
        curr.started = true;
        boolean cycle = false;
        for (Vertex v : curr.others)
        {
            cycle |= dfs(v);
        }
        curr.finished = true;
        return cycle;
    }

    private class Vertex
    {
        ArrayList<Vertex> others;
        boolean started, finished;

        public Vertex()
        {
            others = new ArrayList<>();
        }
    }

    public void ntok() throws IOException
    {
        tok = new StringTokenizer(in.readLine());
    }

    public int ipar()
    {
        return Integer.parseInt(tok.nextToken());
    }

    public long lpar()
    {
        return Long.parseLong(tok.nextToken());
    }

    public double dpar()
    {
        return Double.parseDouble(tok.nextToken());
    }

    public String spar()
    {
        return tok.nextToken();
    }

    public static void main(String[] args) throws IOException
    {
        new D().go();
    }
}