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, time
from os import path
from collections import *
from heapq import *
from math import *

#################### Write your code here ######################

def dfs (v, adj, ans, vis) :
	vis[v] = 1
	for x in adj[v] :
		if vis[x[0]] == 0 :
			dfs(x[0], adj, ans, vis)
			ans[x[1]] = 1
		elif vis[x[0]] == 1 : ans[x[1]] = 2
		else : ans[x[1]] = 1
	vis[v] = 2

def solve (kkkk):
	n, m = inm()
	adj = [[] for i in range(n)] 
	vis = crarr(0, n)
	ans = crarr(0, m)
	for i in range(m) :
		u, v = inm()
		u -= 1; v -= 1;
		adj[u].append((v,i))
	for i in range(n) :
		if vis[i] == 0: dfs(i, adj, ans, vis)
	out(max(ans))
	outa(ans)
	

def main():
    t = 1
    # t = inp()
    for i in range(t):	solve(i + 1)

############################# END ##############################
######################## DO NOT TOUCH ##########################

#--------------------- Local Setup Helper ---------------------#

localsys = 0
start_time = time.time()
if (path.exists('input.txt')):
    sys.stdin  = open("input.txt", "r")
    sys.stdout = open("output.txt","w")
    localsys = 1

#-------------------- I/O Functionalities ---------------------#

cin  = sys.stdin.readline
cout = sys.stdout.write
def inp(): return int(cin().strip())
def ins(): return list(cin().strip())
def inm(): return map(int, cin().strip().split())
def ina(): return list(map(int, cin().strip().split()))

def out  (a) : cout(str(a) + "\n")
def outa (a) : cout(" ".join(map(str, a)) + "\n")
def outm (a, b, c = None, d = None) :
	cout(str(a) + " " + str(b))
	if c != None : cout(" " + str(c))
	if d != None : cout(" " + str(d))
	cout("\n")
	
#--------------------- Helper functions -----------------------#

def crarr (a, n) : return [a for i in range(n)] 

#---------------------- Code Initiator ------------------------#

main()
if localsys:
	print("\n\nTime Elapsed :",time.time() - start_time,"seconds")

################################################################