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:
// package Quarantine;

import javafx.util.Pair;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.StringTokenizer;

public class ColoringEdges {
    static ArrayList<Integer> graph[];
    static boolean visited[];
    static HashMap<Pair<Integer,Integer>,Integer> map;
    static boolean stack[];
    public static void main(String[] args)throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        int n=Integer.parseInt(st.nextToken());
        int m=Integer.parseInt(st.nextToken());
        graph=new ArrayList[n+1];
        for(int i=1;i<=n;i++){
            graph[i]=new ArrayList<>();
        }
        ArrayList<Pair<Integer,Integer>> edges=new ArrayList<>();
        for(int i=1;i<=m;i++){
            st=new StringTokenizer(br.readLine());
            int u=Integer.parseInt(st.nextToken());
            int v=Integer.parseInt(st.nextToken());
            graph[u].add(v);
            edges.add(new Pair<>(u,v));
        }
        map=new HashMap<>();
        stack=new boolean[n+1];
        visited=new boolean[n+1];
        for(int i=1;i<=n;i++){
            if(!visited[i]){
                dfs(i);
            }
        }
        StringBuilder print=new StringBuilder();
        int max=1;
        for(Pair<Integer,Integer> p:edges){
            int x=map.get(p);
            max=Math.max(max,x);
            print.append(x).append(" ");
        }
        System.out.println(max);
        System.out.println(print.toString());
    }
    public static void dfs(int curr){
        visited[curr]=true;
//        System.out.println(curr);
        stack[curr]=true;
        for(int j:graph[curr]){
            if(visited[j]){
                if(stack[j])
                map.put(new Pair<>(curr,j),2);
                else{
                    map.put(new Pair<>(curr,j),1);
                }
            }
            else{
                dfs(j);
                map.put(new Pair<>(curr,j),1);
            }
        }
        stack[curr]=false;
    }
}