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 PYTHON3):

Solution:
import sys
import math
def getAndParseInt(num=1):
    string = (sys.stdin.readline()).strip()
    if num==1:
        return int(string)
    else:
        return [int(part) for part in string.split()]

def getAndParseString(num=1,delim=" "):
    string = (sys.stdin.readline()).strip()
    if num==1:
        return string
    else:
        return [part for part in string.split(delim)]

n, m = getAndParseInt(2)
adj_list = [[] for i in range(n)]
edge_list = []
for i in range(m):
    u, v = getAndParseInt(2)
    edge_list.append((u,v))
    adj_list[u-1].append(v-1)

visited = set()
stack = []
finished_exploring = [False for i in range(n)]
edge_colors = {}
acyclic = True

for i in range(n):
    if i not in visited:
        stack.append((i,0))
    else:
        continue
    while stack:
        cur_vertex, neigh_index = stack.pop()
        if neigh_index == 0:
            visited.add(cur_vertex)

        if neigh_index == len(adj_list[cur_vertex]):
            finished_exploring[cur_vertex] = True
        else:
            stack.append((cur_vertex, neigh_index + 1))
            neighbor = adj_list[cur_vertex][neigh_index]
            if neighbor not in visited:
                stack.append((neighbor, 0))
                edge_colors[(cur_vertex+1,neighbor+1)]='1'
                visited.add(neighbor)
            elif neighbor in visited and not finished_exploring[neighbor]:
                edge_colors[(cur_vertex+1,neighbor+1)]='2'
                acyclic = False
            else:
                edge_colors[(cur_vertex+1,neighbor+1)]='1'

if acyclic:
    print(1)
    output_list = ["1" for i in range(m)]
else:
    print(2)
    output_list = []
    for edge in edge_list:
        output_list.append(edge_colors[edge])
print(" ".join(output_list))