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 random

# arr1=[random.randint(1,100) for i in range(10)]
# arr2=[random.randint(1,100) for i in range(10)]

# print(arr1,"			SORTED:-",sorted(arr1))
# print(arr2,"			SORTED:-",sorted(arr2))


# def brute_inv(a1,a2):
# 	a3=a1+a2
# 	inv=0
# 	for i in range(len(a3)):
# 		for j in range(i+1,len(a3)):
# 			if a3[i]>a3[j]:
# 				inv+=1
# 	return inv

# def smart_inv(arr1,arr2):
# 	i1,i2=0,0
# 	inv1=0;
# 	while i1<len(arr1) and i2<len(arr2):
# 		if arr1[i1]>arr2[i2]:
# 			inv1+=(len(arr1)-i1)
# 			i2+=1
# 		else:
# 			i1+=1
# 	return inv1

# print(arr1+arr2,smart_inv(sorted(arr1),sorted(arr2)))
# print(brute_inv(arr1,arr2))
# print(arr2+arr1,smart_inv(sorted(arr2),sorted(arr1)))
# print(brute_inv(arr2,arr1))

# if (smart_inv(sorted(arr1),sorted(arr2))<smart_inv(sorted(arr2),sorted(arr1)) and brute_inv(arr1,arr2)<brute_inv(arr2,arr1)) or (smart_inv(sorted(arr2),sorted(arr1))<smart_inv(sorted(arr1),sorted(arr2)) and brute_inv(arr2,arr1)<brute_inv(arr1,arr2)):
# 	print("True")
# else:
# 	print("False")


# print(brute_inv([1,2,10],[3,5,7]))
# print(brute_inv([3,5,7],[1,2,10]))
# print(brute_inv([1,7,10],[3,5,17]))
# print(brute_inv([3,5,17],[1,7,10]))

# 1		:-	1
# 2		:-	10
# 3		:-	011
# 4		:-	0100
# 5		:-	00101
# 6		:-	000110
# 7		:-	0000111
# 8		:-	00001000
# 9		:-	000001001
# 10		:-	0000001010
# 11		:-	00000001011
# 12		:-	000000001100
# 13		:-	0000000001101
# 14		:-	00000000001110
# 15		:-	000000000001111
# 16		:-	0000000000010000






















from sys import stdin,stdout

n,m=stdin.readline().strip().split(' ')
n,m=int(n),int(m)
adj=[[] for i in range(n+1)]

for i in range(m):
	u,v=stdin.readline().strip().split(' ')
	u,v=int(u),int(v)
	adj[u].append((v,i))

visited=[0 for i in range(n+1)]
color=['1' for i in range(m)]
flag=1
def dfs(curr):
	global flag
	visited[curr]=1
	for i in adj[curr]:
		if visited[i[0]]==0:
			dfs(i[0])
		elif visited[i[0]]==1:
			color[i[1]]='2'
			flag=2
	visited[curr]=2


for n in range(1,n+1):
	if visited[n]==0:
		dfs(n)

if flag==1:
	stdout.write("1\n");
	stdout.write(' '.join(color)+"\n")
else:
	stdout.write("2\n")
	stdout.write(' '.join(color)+"\n")