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 \le n \le 5000$, $1 \le m \le 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 \le u, v \le n$, $u \ne 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, \dots, c_m$ ($1 \le c_i \le 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

Source: codeforces | Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Constructive algorithms


Solutions:
(n, m) = [int(i) for i in input().split()]
data = []
chil = []
for i in range(n + 1):
	chil.append(set())
for j in range(m):
	data.append([int(i) for i in input().split()])
	chil[data[-1][0]].add(data[-1][1])

def cycle():
	for i in range(1, n + 1):
		stack = [i]
		fnd = [0] * (n + 1)
		while stack:
			s = stack.pop()
			for c in chil[s]:
				if c == i:
					return True
				if not fnd[c]:
					stack.append(c)
					fnd[c] = 1
if not cycle():
	print(1)
	l = ['1' for i in range(m)]
	print(' '.join(l))
else:
	print(2)
	for d in data:
		print(['2', '1'][d[0] < d[1]], end=' ')
	print()


(n, m) = list(map(int, input().split()))
numedge = {}
graph = {}
for v in range(1, n + 1):
	graph[v] = set()
for i in range(m):
	(a, b) = list(map(int, input().split()))
	numedge[a, b] = i
	graph[a].add(b)
visit = {}
par = {}
(s, f) = (-1, -1)

def dfs(v):
	nonlocal s, f
	visit[v] = 1
	for u in graph[v]:
		if u not in visit:
			par[u] = v
			dfs(u)
		elif visit[u] == 1:
			s = u
			f = v
			break
	visit[v] = -1
for v in graph:
	dfs(v)
if s == f == -1:
	print(1)
	print('1 ' * m)
else:
	print(2)
	ans = [0] * m
	for x in graph:
		for y in graph[x]:
			ans[numedge[x, y]] = (x > y) + 1
	print(*ans)


(n, m) = [int(x) for x in input().split()]
dic = {}
paint = {}
cycle = False
edges = []
for i in range(m):
	(a, b) = [int(x) for x in input().split()]
	edges.append((a, b))
	if a not in dic:
		dic[a] = set([b])
	else:
		dic[a].add(b)
inv = [False] * (n + 1)
invite = [False] * (n + 1)

def gcd(n):
	paint[n] = 0
	invite[n] = True
	if n in dic:
		for item in dic[n]:
			if not invite[item]:
				if gcd(item):
					return True
			elif paint[item] == 0:
				return True
	paint[n] = 1
	return False
for item in range(1, n + 1):
	if not invite[item]:
		cycle = gcd(item) or cycle
arr = []
if cycle:
	print(2)
	for item in edges:
		if item[0] < item[1]:
			arr.append(1)
		else:
			arr.append(2)
else:
	print(1)
	for item in edges:
		arr.append(1)
print(*arr)


import sys
import collections
import functools
(n, m) = map(int, input().strip().split())
graph = collections.defaultdict(list)
edges = []
for i in range(m):
	(u, v) = map(int, input().strip().split())
	graph[u].append([v, i])
	edges.append((u, v))
ans = [1] * m
visited = set()

def dfs(u, seen):
	seen.add(u)
	visited.add(u)
	for (v, i) in graph[u]:
		if v in seen:
			ans[i] = 2
		elif v not in visited:
			ans[i] = 1
			dfs(v, seen)
	seen.remove(u)
seen = set()
for (u, v) in edges:
	if u in visited:
		continue
	dfs(u, seen)
print(max(ans))
print(' '.join((str(i) for i in ans)))


(n, m) = input().split()
n = int(n)
m = int(m)
ady = [[] for _ in range(n + 1)]
color = [0] * (n + 1)
oneColor = True
sol = [0] * m

def dfs_visit(v):
	global sol, ady, oneColor, color
	color[v] = 1
	for par in ady[v]:
		(u, index) = (par[0], par[1])
		if color[u] == 0:
			dfs_visit(u)
			sol[index] = 1
		elif color[u] == 2:
			sol[index] = 1
		else:
			sol[index] = 2
			oneColor = False
	color[v] = 2
for i in range(m):
	(n1, n2) = input().split()
	n1 = int(n1)
	n2 = int(n2)
	ady[n1].append((n2, i))
for v in range(1, n + 1):
	if color[v] == 0:
		dfs_visit(v)
if oneColor:
	print(1)
else:
	print(2)
res = str('')
for i in range(0, m):
	res += str(sol[i]) + str(' ')
print(res)


def iscyclic(s, visited, restack):
	visited[s] = True
	restack[s] = True
	if s in adj:
		for u in adj[s]:
			if visited[u] == False:
				if iscyclic(u, visited, restack) == True:
					return True
			elif restack[u] == True:
				return True
	restack[s] = False
	return False

def cyclic():
	visited = [False] * (n + 1)
	restack = [False] * (n + 1)
	for u in adj:
		if visited[u] == False:
			if iscyclic(u, visited, restack) == True:
				return True
	return False
(n, m) = map(int, input().split())
adj = {}
l = []
for i in range(m):
	(a, b) = map(int, input().split())
	if a not in adj:
		adj[a] = [b]
	else:
		adj[a].append(b)
	l.append([a, b])
visited = [False] * (n + 1)
bo = cyclic()
if bo == False:
	print(1)
	for i in range(m):
		print(1, end=' ')
else:
	print(2)
	for i in range(m):
		if l[i][0] > l[i][1]:
			print(2, end=' ')
		else:
			print(1, end=' ')


(v_n, e_n) = tuple(map(int, input().split()))
G = [set() for _ in range(v_n)]
edges = []
d_s = [-1] * v_n
ok = False

def dfs(u):
	nonlocal ok
	if ok:
		return
	d_s[u] = 0
	for v in G[u]:
		if d_s[v] == -1:
			dfs(v)
		elif d_s[v] == 0:
			ok = True
	d_s[u] = 1
for _ in range(e_n):
	(u, v) = tuple(map(int, input().split()))
	u -= 1
	v -= 1
	edges.append((u, v))
	G[u].add(v)
for u in range(v_n):
	if d_s[u] == -1:
		dfs(u)
if not ok:
	print(1)
	for _ in range(e_n):
		print(1, end=' ')
else:
	print(2)
	for (u, v) in edges:
		print(int(u < v) + 1, end=' ')


vis = []
ans = []
nodes = []

def dfs(A):
	nonlocal vis, ans, nodes
	vis[A] = 1
	for (B, index) in nodes[A]:
		if ans[index] != 0:
			continue
		if vis[B] == 1:
			ans[index] = 2
		else:
			ans[index] = 1
			dfs(B)
	vis[A] = 2

def main():
	nonlocal vis, ans, nodes
	(n, m) = map(int, input().strip().split())
	vis = [-1] * (n + 10)
	ans = [0] * (m + 10)
	nodes = [[] for i in range(n + 10)]
	for i in range(m):
		(a, b) = map(int, input().strip().split())
		nodes[a].append((b, i))
	for i in range(1, n + 1):
		if vis[i] == -1:
			dfs(i)
	if 2 in ans:
		print(2)
	else:
		print(1)
	for i in range(m):
		print(ans[i])

def __starting_point():
	main()
__starting_point()


(n, m) = input().split()
n = int(n)
m = int(m)
ady = [[] for _ in range(n + 1)]
low = [0] * (n + 1)
vdfs = [0] * (n + 1)
ndfs = int(0)
oneColor = True
mark = [False] * (n + 1)
sol = [0] * m

def dfs(nod):
	global sol, ndfs, ady, vdfs, low, oneColor, ant, pila
	ndfs += 1
	vdfs[nod] = low[nod] = ndfs
	for par in ady[nod]:
		to = par[0]
		index = par[1]
		sol[index] = 1
		if vdfs[to] == 0:
			dfs(to)
			low[nod] = min(low[to], low[nod])
		elif mark[to] == False:
			low[nod] = min(low[nod], vdfs[to])
			if low[to] <= vdfs[nod]:
				oneColor = False
				sol[index] = 2
	mark[nod] = True
for i in range(m):
	(n1, n2) = input().split()
	n1 = int(n1)
	n2 = int(n2)
	ady[n1].append((n2, i))
for i in range(1, n + 1):
	if vdfs[i] == 0:
		dfs(i)
if oneColor:
	print(1)
else:
	print(2)
res = str('')
for i in range(0, m):
	res += str(sol[i]) + str(' ')
print(res)


def main():
	import sys
	from collections import deque
	input = sys.stdin.readline
	(N, M) = map(int, input().split())
	adj = [[] for _ in range(N + 1)]
	edge = {}
	in_num = [0] * (N + 1)
	for i in range(M):
		(a, b) = map(int, input().split())
		adj[a].append(b)
		edge[a * (N + 1) + b] = i
		in_num[b] += 1
	ans = [1] * M
	que = deque()
	for i in range(1, N + 1):
		if in_num[i] == 0:
			que.append(i)
	j = 0
	cnt = 0
	while True:
		while que:
			v = que.pop()
			cnt += 1
			for u in adj[v]:
				in_num[u] -= 1
				if in_num[u] == 0:
					que.append(u)
		if cnt == N:
			break
		else:
			while True:
				if in_num[j] <= 0:
					j += 1
				else:
					break
			in_num[j] = -1
			cnt += 1
			for u in adj[j]:
				ans[edge[j * (N + 1) + u]] = 2
				in_num[u] -= 1
				if in_num[u] == 0:
					que.append(u)
				elif in_num[u] < 0:
					ans[edge[j * (N + 1) + u]] = 1
	print(max(ans))
	print(*ans)
main()


(n, m) = [int(item) for item in input().split()]
edge = [[] for _ in range(n)]
visited = [False] * n
raw = []
for i in range(m):
	(a, b) = [int(item) for item in input().split()]
	a -= 1
	b -= 1
	raw.append((a, b))
	edge[a].append(b)

class DirectedGraph:

	def __init__(self, adj):
		self.n = len(adj)
		self.adj = adj
		self.is_asyclic = False
		self.max_path_len = None

	def topological_sort(self):
		indegree = [0] * self.n
		for (i, vs) in enumerate(self.adj):
			for dest in vs:
				indegree[dest] += 1
		zero_v = []
		for (v, indeg) in enumerate(indegree):
			if indeg == 0:
				zero_v.append(v)
		max_path_len = 1
		tp_sorted = []
		to_be_added = []
		while True:
			while zero_v:
				v = zero_v.pop()
				tp_sorted.append(v)
				for dest in self.adj[v]:
					indegree[dest] -= 1
					if indegree[dest] == 0:
						to_be_added.append(dest)
			if len(to_be_added) > 0:
				zero_v += to_be_added
				to_be_added = []
				max_path_len += 1
			else:
				break
		if len(tp_sorted) == self.n:
			self.is_asyclic = True
			self.max_path_len = max_path_len
			return tp_sorted
		else:
			self.is_asyclic = False
			return None
DG = DirectedGraph(edge)
tp_sorted = DG.topological_sort()
if DG.is_asyclic:
	print(1)
	print(' '.join(['1' for _ in range(m)]))
	return
else:
	print(2)
	ans = []
	for (a, b) in raw:
		if a > b:
			ans.append(1)
		else:
			ans.append(2)
	print(' '.join([str(item) for item in ans]))


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
EDGE = [tuple(map(int, input().split())) for i in range(m)]
E = [[] for i in range(n + 1)]
EDGEIN = [0] * (n + 1)
EDGEOUTLIST = [[] for i in range(n + 1)]
for (x, y) in EDGE:
	EDGEIN[y] += 1
	EDGEOUTLIST[x].append(y)
from collections import deque
QUE = deque()
for i in range(1, n + 1):
	if EDGEIN[i] == 0:
		QUE.append(i)
TOP_SORT = []
while QUE:
	x = QUE.pop()
	TOP_SORT.append(x)
	for to in EDGEOUTLIST[x]:
		EDGEIN[to] -= 1
		if EDGEIN[to] == 0:
			QUE.appendleft(to)
if len(TOP_SORT) == n:
	print(1)
	print(*[1] * m)
else:
	print(2)
	for (x, y) in EDGE:
		if x > y:
			print(1, end=' ')
		else:
			print(2, end=' ')


from collections import deque

def DFS(x, color, solucion):
	color[x] = 1
	c = False
	for (y, i) in adyacentes[x]:
		if color[y] == 0:
			c = DFS(y, color, solucion) or c
			solucion[i] = 1
		elif color[y] == 2:
			solucion[i] = 1
		else:
			solucion[i] = 2
			c = True
	color[x] = 2
	return c

def Solucion():
	color = [0] * n
	solucion = [0] * m
	c = False
	for l in range(0, n):
		if color[l] == 0:
			c = DFS(l, color, solucion) or c
	print(2 if c else 1)
	print(*solucion, sep=' ')
(n, m) = map(int, input().split())
adyacentes = [[] for _ in range(0, n)]
for i in range(0, m):
	(u, v) = map(lambda x: int(x) - 1, input().split())
	adyacentes[u].append((v, i))
Solucion()


import os
import sys
from collections import defaultdict

def get_adj(edges):
	neighbors = defaultdict(list, {})
	for (v1, v2) in edges:
		neighbors[v1].append(v2)
	return dict(neighbors)
NEW = 0
VISITING = 1
CLOSED = 2

def solve(edges, n):
	adj = get_adj(edges)
	status = [NEW] * (n + 1)
	edge_idx = {tuple(e): idx for (idx, e) in enumerate(edges)}
	colors = [1] * len(edges)
	has_loop = [False]

	def dfs(root):
		if status[root] == CLOSED:
			return
		status[root] = VISITING
		children = adj.get(root, [])
		for c in children:
			if status[c] == NEW:
				dfs(c)
			elif status[c] == VISITING:
				colors[edge_idx[root, c]] = 2
				has_loop[0] = True
			elif status[c] == CLOSED:
				pass
		status[root] = CLOSED
	for i in range(1, n + 1):
		dfs(i)
	return (has_loop[0], colors)

def pp(input):
	(n, m) = map(int, input().strip().split())
	edges = [tuple(map(int, input().strip().split())) for _ in range(m)]
	(has_loop, colors) = solve(edges, n)
	print(int(has_loop) + 1)
	print(' '.join(map(str, colors)))
if 'pydev' in sys.argv[0]:
	from string_source import string_source, codeforces_parse
	x = 'inputCopy\n4 5\n1 2\n1 3\n3 4\n2 4\n1 4\noutputCopy\n1\n1 1 1 1 1 \ninputCopy\n3 3\n1 2\n2 3\n3 1\noutputCopy\n2\n1 1 2 '
	for (q, a) in codeforces_parse(x):
		pp(string_source(q))
		print(a)
		print('----')
else:
	pp(sys.stdin.readline)


import sys
sys.setrecursionlimit(10 ** 9)

def dfs(a):
	nonlocal adj, vis, st
	j = 0
	vis[a] = 1
	for i in adj[a][:]:
		if vis[i[0]] == 0:
			dfs(i[0])
			adj[a][j][1] = 1
		elif vis[i[0]] == 2:
			adj[a][j][1] = 1
		else:
			st = 2
			adj[a][j][1] = 2
		j += 1
	vis[a] = 2
(n, m) = list(map(int, input().split()))
it = []
adj = [[] for i in range(n)]
for _ in range(m):
	(a, b) = list(map(int, input().split()))
	adj[a - 1].append([b - 1, 1, _])
vis = [0] * n
st = 1
for ii in range(n):
	if vis[ii] == 0:
		dfs(ii)
print(st)
ans = [0] * m
for i in range(n):
	for j in adj[i]:
		ans[j[2]] = j[1]
print(*ans)


from sys import stdin, stdout
time = 0
k = 1

def dfs(node: int, graph):
	stack = []
	global time
	global k
	stack.append(node)
	while stack:
		s = stack.pop()
		if d[s] == -1:
			d[s] = time
			time += 1
			stack.append(s)
			for (v, i) in graph[s]:
				if d[v] == -1:
					colour[i] = '1'
					stack.append(v)
				elif f[v] == -1:
					k = 2
					colour[i] = '2'
				else:
					colour[i] = '1'
		elif f[s] == -1:
			f[s] = time
			time += 1
(n, m) = [int(x) for x in stdin.readline().split()]
graph = [[] for _ in range(n)]
for i in range(m):
	(u, v) = stdin.readline().split()
	(u, v) = (int(u) - 1, int(v) - 1)
	graph[u].append((v, i))
d = [-1] * n
f = [-1] * n
pi = [-1] * n
colour = ['1'] * m
for i in range(n):
	if d[i] == -1:
		dfs(i, graph)
stdout.write(f'{k}\n')
col = ' '.join(colour)
col += '\n'
stdout.write(col)


from collections import defaultdict
ans = defaultdict(lambda : 1)
flag = 0

def dfs(i):
	nonlocal flag
	vis[i] = 1
	for j in hash[i]:
		if not vis[j]:
			dfs(j)
		elif vis[j] == 1:
			flag = 1
			ans[i, j] = 2
	vis[i] = 2
(n, m) = map(int, input().split())
hash = defaultdict(list)
par = [0] + [i + 1 for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	hash[a].append(b)
	ans[a, b] = 1
vis = [0] * (n + 1)
for i in range(n):
	if vis[i] == 0:
		dfs(i)
if flag:
	print(2)
else:
	print(1)
for i in ans:
	print(ans[i], end=' ')


from collections import defaultdict
import sys, math
f = None
try:
	f = open('q1.input', 'r')
except IOError:
	f = sys.stdin
if 'xrange' in dir(__builtins__):
	range = xrange

def print_case_iterable(case_num, iterable):
	print('Case #{}: {}'.format(case_num, ' '.join(map(str, iterable))))

def print_case_number(case_num, iterable):
	print('Case #{}: {}'.format(case_num, iterable))

def print_iterable(A):
	print(' '.join(A))

def read_int():
	return int(f.readline().strip())

def read_int_array():
	return [int(x) for x in f.readline().strip().split(' ')]

def rns():
	a = [x for x in f.readline().split(' ')]
	return (int(a[0]), a[1].strip())

def read_string():
	return list(f.readline().strip())

def ri():
	return int(f.readline().strip())

def ria():
	return [int(x) for x in f.readline().strip().split(' ')]

def rns():
	a = [x for x in f.readline().split(' ')]
	return (int(a[0]), a[1].strip())

def rs():
	return list(f.readline().strip())

def bi(x):
	return bin(x)[2:]
from collections import deque
import math
NUMBER = 10 ** 9 + 7

def factorial(n):
	M = NUMBER
	f = 1
	for i in range(1, n + 1):
		f = f * i % M
	return f

def mult(a, b):
	return a * b % NUMBER

def minus(a, b):
	return (a - b) % NUMBER

def plus(a, b):
	return (a + b) % NUMBER

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a):
	m = NUMBER
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	if n < k:
		assert false
	return mult(factorial(n), modinv(mult(factorial(k), factorial(n - k)))) % NUMBER
from collections import deque, defaultdict
import heapq
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

def dfs(g, timeIn, timeOut, depths, parents):
	cnt = 0
	stack = [[1, 0, 0, 0]]
	while stack:
		(v, neig_i, parent, depth) = stack[-1]
		parents[v] = parent
		depths[v] = depth
		if neig_i == 0:
			timeIn[v] = cnt
			cnt += 1
		while neig_i < len(g[v]):
			u = g[v][neig_i]
			if u == parent:
				neig_i += 1
				continue
			stack[-1][1] = neig_i + 1
			stack.append([u, 0, v, depth + 1])
			break
		if neig_i == len(g[v]):
			stack.pop()
			timeOut[v] = cnt
			cnt += 1
cnt = 0

@bootstrap
def dfs(v, adj, timeIn, timeOut, depths, parents, parent=0, depth=0):
	global cnt
	parents[v] = parent
	depths[v] = depth
	timeIn[v] = cnt
	cnt += 1
	for u in adj[v]:
		if u == parent:
			continue
		yield dfs(u, adj, timeIn, timeOut, depths, parents, v, depth + 1)
	timeOut[v] = cnt
	cnt += 1
	yield

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a * b / gcd(a, b)

def get_num_2_5(n):
	twos = 0
	fives = 0
	while n > 0 and n % 2 == 0:
		n //= 2
		twos += 1
	while n > 0 and n % 5 == 0:
		n //= 5
		fives += 1
	return (twos, fives)

def shift(a, i, num):
	for _ in range(num):
		(a[i], a[i + 1], a[i + 2]) = (a[i + 2], a[i], a[i + 1])

def equal(x, y):
	return abs(x - y) <= 1e-09

def getAngle(a, b, c):
	ang = math.degrees(math.atan2(c[1] - b[1], c[0] - b[0]) - math.atan2(a[1] - b[1], a[0] - b[0]))
	return ang + 360 if ang < 0 else ang

def getLength(a, b):
	return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)
from heapq import heapify, heappush, heappop

def bfs(adj):
	s = set()
	d = defaultdict(set)
	q = deque([])
	s.add(0)
	d[0].add(0)
	q.append((0, 0))
	while len(q) > 0:
		(v, depth) = q.popleft()
		for u in adj[v]:
			if u not in s:
				s.add(u)
				d[depth + 1].add(u)
				q.append((u, depth + 1))
	return d

def isSubsetSum(arr, n, summ):
	subarr = [[False for i in range(summ + 1)] for i in range(n + 1)]
	for i in range(n + 1):
		subarr[i][0] = True
	for i in range(1, summ + 1):
		subarr[0][i] = False
	for i in range(1, n + 1):
		for j in range(1, summ + 1):
			if j < arr[i - 1]:
				subarr[i][j] = subarr[i - 1][j]
			if j >= arr[i - 1]:
				subarr[i][j] = subarr[i - 1][j] or subarr[i - 1][j - arr[i - 1]]
	return subarr[n][summ]

@bootstrap
def dfs(v, adj, vis, black):
	vis[v] = 1
	for u in adj[v]:
		if vis[u] == 2:
			continue
		if vis[u] == 1:
			black.add((v, u))
			continue
		yield dfs(u, adj, vis, black)
	vis[v] = 2
	yield

def solution(adj, n, m, edges, edge_list):
	black = set()
	vis = [0 for _ in range(n)]
	for v in range(n):
		if vis[v]:
			continue
		dfs(v, adj, vis, black)
	res = []
	for e in edge_list:
		if e in black:
			res.append(2)
		else:
			res.append(1)
	return f'{(2 if black else 1)}' + '\n' + ' '.join(map(str, res))

def main():
	T = 1
	for i in range(T):
		(n, m) = ria()
		adj = [list() for _ in range(n)]
		edges = dict()
		edge_list = []
		for _ in range(m):
			(a, b) = ria()
			a -= 1
			b -= 1
			adj[a].append(b)
			edges[a, b] = _
			edge_list.append((a, b))
		x = solution(adj, n, m, edges, edge_list)
		if 'xrange' not in dir(__builtins__):
			print(x)
		else:
			(print >> output, str(x))
	if 'xrange' in dir(__builtins__):
		print(output.getvalue())
		output.close()
if 'xrange' in dir(__builtins__):
	import cStringIO
	output = cStringIO.StringIO()
main()


colors = 1
(n, m) = map(int, input().split(' '))
adj = [[] for i in range(n)]
color = [0 for i in range(m)]
vis = [0 for i in range(n)]

def dfs(u):
	global colors
	vis[u] = 1
	for (i, v) in adj[u]:
		if vis[v] == 1:
			colors = 2
			color[i] = 2
		else:
			color[i] = 1
			if vis[v] == 0:
				dfs(v)
	vis[u] = 2
for i in range(m):
	(u, v) = map(int, input().split(' '))
	adj[u - 1].append((i, v - 1))
for i in range(n):
	if vis[i] == 0:
		dfs(i)
print(colors)
print(' '.join(map(str, color)))


import math
(n, m) = [int(i) for i in input().split(' ')]
d = [[] for i in range(n)]
done = [False for i in range(n)]

def dfs(visited, i, d):
	visited[i] = True
	done[i] = True
	for j in d[i]:
		if visited[j]:
			return True
		if not done[j]:
			temp = dfs(visited, j, d)
			if temp:
				return True
	visited[i] = False
	return False
edgelist = []
for i in range(m):
	(a, b) = [int(i) for i in input().split(' ')]
	edgelist.append([a, b])
	d[a - 1].append(b - 1)
ans = 0
visited = [False for i in range(n)]
for i in range(n):
	if dfs(visited, i, d):
		ans = 1
		break
if ans:
	print(2)
	for i in edgelist:
		if i[0] > i[1]:
			print(2, end=' ')
		else:
			print(1, end=' ')
else:
	print(1)
	print(' '.join(('1' for i in range(m))))


import sys
import collections
import functools
(n, m) = list(map(int, input().strip().split()))
graph = collections.defaultdict(list)
edges = []
for i in range(m):
	(u, v) = list(map(int, input().strip().split()))
	graph[u].append([v, i])
	edges.append((u, v))
ans = [1] * m
visited = [False for _ in range(5000)]
seen = [False for _ in range(5000)]

def dfs(u):
	seen[u] = visited[u] = True
	for (v, i) in graph[u]:
		if seen[v]:
			ans[i] = 2
		elif not visited[v]:
			ans[i] = 1
			dfs(v)
	seen[u] = False
for (u, v) in edges:
	if visited[u]:
		continue
	dfs(u)
print(max(ans))
print(' '.join((str(i) for i in ans)))


def DFS(graph, status, v):
	status[v] = 1
	for u in graph[v]:
		if status[u] == 1:
			return True
		if status[u] == 0:
			if DFS(graph, status, u):
				return True
	status[v] = 2

def containsCycle(graph):
	n = len(graph)
	status = [0] * n
	for v in range(n):
		if status[v] != 0:
			continue
		if DFS(graph, status, v):
			return True
	return False
nm = input().split()
n = int(nm[0])
m = int(nm[1])
graph = [set() for _ in range(n)]
edges = []
for _ in range(m):
	edge = input().split()
	u = int(edge[0]) - 1
	v = int(edge[1]) - 1
	edges.append((u, v))
	graph[u].add(v)
if not containsCycle(graph):
	print(1)
	answer = [1] * m
	print(*answer)
else:
	print(2)
	answer = []
	for e in edges:
		if e[0] > e[1]:
			answer.append(1)
		else:
			answer.append(2)
	print(*answer)


(n, m) = input().split(' ')
(n, m) = (int(n), int(m))
ch = [[] for i in range(n + 1)]
edges_by_order = []
for i in range(m):
	(x, y) = input().split(' ')
	(x, y) = (int(x), int(y))
	ch[x].append(y)
	edges_by_order.append((x, y))
for i in range(n + 1):
	ch[i] = sorted(ch[i])
st = [0 for i in range(n + 1)]
end = [0 for i in range(n + 1)]
timestamp = 0
cycle_exists = False

def dfs(x):
	nonlocal ch, st, end, timestamp, cycle_exists
	timestamp += 1
	st[x] = timestamp
	for y in ch[x]:
		if st[y] == 0:
			dfs(y)
		elif st[y] < st[x] and end[y] == 0:
			cycle_exists = True
	timestamp += 1
	end[x] = timestamp
for i in range(1, n + 1):
	if st[i] == 0:
		dfs(i)
if not cycle_exists:
	print(1)
	for i in range(m):
		print(1, end=' ')
	print('', end='\n')
else:
	print(2)
	for i in range(m):
		x = st[edges_by_order[i][0]]
		y = st[edges_by_order[i][1]]
		if x < y:
			print(1, end=' ')
		else:
			print(2, end=' ')
	print('', end='\n')


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):
	nonlocal 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')


(n, m) = map(int, input().split())
AE = []
E = [[] for _ in range(n)]
di = [0] * n
do = [0] * n
ok = True

def DFS(u):
	nonlocal ok
	di[u] = True
	for v in E[u]:
		if di[v]:
			if not do[v]:
				ok = False
			continue
		DFS(v)
	do[u] = True
for _ in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	AE.append((u, v))
	E[u].append(v)
for i in range(n):
	if not di[i]:
		DFS(i)
if ok:
	print(1)
	for _ in range(m):
		print(1, end=' ')
else:
	print(2)
	for (u, v) in AE:
		print(int(u < v) + 1, end=' ')


(n, m) = map(int, input().split())
L = []
for i in range(n):
	s = []
	L.append(s)
st = []
for i in range(m):
	(u, v) = map(int, input().split())
	st.append((u - 1, v - 1))
	L[u - 1].append(v - 1)
visited = [False] * n
rs = [False] * n

def dfs(u):
	if visited[u] == False:
		visited[u] = True
		rs[u] = True
		for i in L[u]:
			if visited[i] == False and dfs(i) == True:
				return True
			elif rs[i] == True:
				return True
	rs[u] = False
	return False
flag = 0
for i in range(0, n):
	if dfs(i) == True:
		flag = 1
		break
if flag == 0:
	print(1)
	for i in range(m):
		print(1, end=' ')
	print(' ')
else:
	print(2)
	for i in range(0, len(st)):
		if st[i][0] < st[i][1]:
			print(1, end=' ')
		else:
			print(2, end=' ')
	print(' ')


def dfs(inp, stat, u):
	if stat[u] > 1:
		return stat[u] < 3
	stat[u] = 2
	for v in inp[u]:
		if dfs(inp, stat, v):
			return True
	stat[u] = 3
	return False

def main():
	ans = []
	(n, m) = list(map(int, input().split()))
	inp = tuple(([] for _ in range(n + 1)))
	for _ in range(m):
		(u, v) = list(map(int, input().split()))
		ans.append((u > v) + 1)
		inp[u].append(v)
	stat = [1] * (n + 1)
	for u in range(n + 1):
		if dfs(inp, stat, u):
			print(2)
			print(*ans)
			break
	else:
		print(1)
		print(*(1,) * m)
main()


from collections import defaultdict, deque
import sys
import bisect
input = sys.stdin.readline
(n, m) = map(int, input().split())
graph = [tuple(map(int, input().split())) for i in range(m)]
e = [[] for i in range(n + 1)]
e_in = [0] * (n + 1)
e_out = [[] for i in range(n + 1)]
for (x, y) in graph:
	e_in[y] += 1
	e_out[x].append(y)
queue = deque()
for i in range(1, n + 1):
	if e_in[i] == 0:
		queue.append(i)
top = []
while queue:
	x = queue.popleft()
	top.append(x)
	for child in e_out[x]:
		e_in[child] -= 1
		if e_in[child] == 0:
			queue.append(child)
if len(top) == n:
	print(1)
	print(*[1] * m)
else:
	print(2)
	for (x, y) in graph:
		if x > y:
			print(1, end=' ')
		else:
			print(2, end=' ')


from sys import stdin
input = stdin.readline
(n, m) = [int(i) for i in input().split()]
edges = [[[0 for i in range(n)], 0] for i in range(n + 1)]
edges_2 = [[0, 0] for i in range(m)]
for i in range(m):
	(v, w) = [int(i) for i in input().split()]
	edges[v][0][edges[v][1]] = w
	edges[v][1] += 1
	edges_2[i] = [v, w]
is_one = True
for i in range(1, n + 1):
	visited = [0 for i in range(n)]
	visited[0] = i
	num_visited = 1
	act = 0
	while act <= num_visited - 1:
		for j in range(edges[visited[act]][1]):
			if edges[visited[act]][0][j] == i:
				is_one = False
			elif edges[visited[act]][0][j] not in visited:
				visited[num_visited] = edges[visited[act]][0][j]
				num_visited += 1
		act += 1
if is_one:
	print(1)
	for i in range(m - 1):
		print('1', end=' ')
	print(1)
else:
	print(2)
	for i in range(m - 1):
		if edges_2[i][0] < edges_2[i][1]:
			print('1', end=' ')
		else:
			print('2', end=' ')
	if edges_2[-1][0] < edges_2[-1][1]:
		print('1')
	else:
		print('2')


class Graph:

	def __init__(self, n, m):
		self.nodes = n
		self.edges = m
		self.adj = [[] for i in range(n)]
		self.color = [0 for i in range(m)]
		self.vis = [0 for i in range(n)]
		self.colors = 1

	def add_edge(self, u, v, i):
		self.adj[u].append((i, v))

	def dfs(self, u):
		self.vis[u] = 1
		for (i, v) in self.adj[u]:
			if self.vis[v] == 1:
				self.colors = 2
				self.color[i] = 2
			else:
				self.color[i] = 1
				if self.vis[v] == 0:
					self.dfs(v)
		self.vis[u] = 2

	def solve(self):
		for i in range(self.nodes):
			if self.vis[i] == 0:
				self.dfs(i)
		print(self.colors)
		print(' '.join(map(str, self.color)))
(n, m) = map(int, input().split(' '))
graph = Graph(n, m)
for i in range(m):
	(u, v) = map(int, input().split(' '))
	graph.add_edge(u - 1, v - 1, i)
graph.solve()


from collections import defaultdict
ans = defaultdict(lambda : 1)
flag = 0

def dfs(node):
	global flag
	visit[node] = 1
	for j in graph[node]:
		if not visit[j]:
			dfs(j)
		elif visit[j] == 1:
			flag = 1
			ans[node, j] = 2
	visit[node] = 2
(n, m) = map(int, input().split())
graph = defaultdict(list)
parent = [0] + [i + 1 for i in range(n)]
for i in range(m):
	(e1, e2) = map(int, input().split())
	graph[e1].append(e2)
	ans[e1, e2] = 1
visit = [0] * (n + 1)
for i in range(n):
	if visit[i] == 0:
		dfs(i)
if flag:
	print(2)
else:
	print(1)
for i in ans:
	print(ans[i], end=' ')


from collections import deque, Counter
import array
from itertools import combinations, permutations
from math import sqrt
import unittest

def read_int():
	return int(input().strip())

def read_int_array():
	return [int(i) for i in input().strip().split(' ')]
(vn, en) = read_int_array()
al = [[] for _ in range(vn)]

def adj(v):
	return al[v]
itoe = [None for _ in range(en)]
for eid in range(en):
	(v, w) = read_int_array()
	v -= 1
	w -= 1
	al[v] += [w]
	itoe[eid] = (v, w)
marked = set()
stack = set()
etoc = {}

def dfs(v):
	if v in marked:
		return
	marked.add(v)
	stack.add(v)
	hasbackedge = False
	for w in adj(v):
		if w in stack:
			hasbackedge = True
			etoc[v, w] = 2
			continue
		if w in marked:
			continue
		if dfs(w):
			hasbackedge = True
	stack.remove(v)
	return hasbackedge
hasbackedge = False
for v in range(vn):
	if v not in marked:
		if dfs(v):
			hasbackedge = True
print(2 if hasbackedge else 1)
for ei in range(en):
	(v, w) = itoe[ei]
	c = etoc.get((v, w), 1)
	print(c, end=' ')


import sys, time
from os import path
from collections import *
from heapq import *
from math import *

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
	for i in range(t):
		solve(i + 1)
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
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')

def crarr(a, n):
	return [a for i in range(n)]
main()
if localsys:
	print('\n\nTime Elapsed :', time.time() - start_time, 'seconds')


[N, M] = list(map(int, input().split()))
edges = [[] for _ in range(N + 1)]
edge_in = []
for _ in range(M):
	[u, v] = list(map(int, input().split()))
	edge_in.append([u, v])
	edges[u].append(v)
seen = [False for _ in range(N + 1)]
visited = [False for _ in range(N + 1)]

def bfs(node):
	visited[node] = True
	seen[node] = True
	for v in edges[node]:
		if not seen[v] and visited[v]:
			continue
		if seen[v] or bfs(v):
			return True
	seen[node] = False
	return False
hasCycle = False
for i in range(1, N + 1):
	if visited[i]:
		continue
	if bfs(i):
		hasCycle = True
		break
if not hasCycle:
	print(1)
	print(' '.join(['1' for _ in range(M)]))
else:
	print(2)
	print(' '.join(['1' if u < v else '2' for (u, v) in edge_in]))


(WHITE, GRAY, BLACK) = (0, 1, 2)

def solve(graph: [], colors: []):
	n = len(graph) - 1
	visited = [WHITE] * (n + 1)
	returnValue = 1
	for i in range(1, n + 1):
		if visited[i] == WHITE and Dfs(graph, colors, i, visited):
			returnValue = 2
	return returnValue

def Dfs(graph: [], colors: [], id, visited: []):
	visited[id] = GRAY
	returnValue = False
	for (adj, colorId) in graph[id]:
		if visited[adj] == WHITE:
			val = Dfs(graph, colors, adj, visited)
			returnValue = True if val else returnValue
		elif visited[adj] == GRAY:
			returnValue = True
			colors[colorId] = 2
	visited[id] = BLACK
	return returnValue
(n, m) = [int(x) for x in input().split()]
graph = [[] for _ in range(n + 1)]
colors = [1] * m
for i in range(m):
	(u, v) = [int(x) for x in input().split()]
	graph[u].append((v, i))
print(solve(graph, colors))
for color in colors:
	print(color, end=' ')
print()


from collections import defaultdict
vis = []

def isCyclic(n, graph):
	global vis
	global k
	vis = [0] * n
	rec = [0] * n
	for i in range(0, n):
		if vis[i] == False:
			if DfsRec(i, rec, graph):
				j = 0
	return False

def DfsRec(i, rec, g):
	global s1
	global s2
	global vis
	global k
	vis[i] = True
	rec[i] = True
	for u in g[i]:
		if vis[u] == False:
			DfsRec(u, rec, g)
		elif rec[u] == True:
			k = 1
			colors[i, u] = 2
			s1 = i
			s2 = u
	rec[i] = False
	return False
(n, e) = list(map(int, input().split()))
d = defaultdict(lambda : [])
colors = defaultdict(lambda : 1)
l = []
for i in range(0, e):
	(a, b) = list(map(int, input().split()))
	l.append([a - 1, b - 1])
	d[a - 1].append(b - 1)
s1 = -1
s2 = -1
k = 0
c = isCyclic(n, d)
if k == 1:
	print(2)
	ans = []
	for (i, j) in l:
		ans.append(colors[i, j])
	print(*ans)
else:
	print(1)
	l = [1] * e
	print(*l)


import sys
input = sys.stdin.readline

def dfs(cur_node, childs, vis, cur_dfs):
	if cur_node in cur_dfs:
		return True
	if vis[cur_node]:
		return False
	vis[cur_node] = True
	cur_dfs.add(cur_node)
	for ele in childs[cur_node]:
		if dfs(ele, childs, vis, cur_dfs):
			return True
	cur_dfs.remove(cur_node)
	return False
(n, m) = map(int, input().split())
childs = [[] for i in range(n + 1)]
has_dad = [False] * (n + 1)
vis = [False] * (n + 1)
ans2 = []
for i in range(m):
	(x1, x2) = map(int, input().split())
	ans2.append(str((x1 < x2) + 1))
	childs[x1].append(x2)
	has_dad[x2] = True
has_cycle = False
for i in range(1, n + 1):
	if not has_dad[i] and dfs(i, childs, vis, set()):
		has_cycle = True
		break
for i in range(1, n + 1):
	if has_dad[i] and (not vis[i]):
		has_cycle = True
		break
if has_cycle:
	print(2)
	print(' '.join(ans2))
else:
	print(1)
	print(' '.join(['1'] * m))


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


def DFS(x, color, adyacentes, solucion):
	color[x] = 1
	c = False
	for (y, i) in adyacentes[x]:
		if color[y] == 0:
			c = DFS(y, color, adyacentes, solucion) or c
		elif color[y] == 1:
			solucion[i] = 2
			c = True
	color[x] = 2
	return c

def ColoringEdges():
	(n, m) = map(int, input().split())
	adyacentes = [[] for _ in range(0, n)]
	for i in range(0, m):
		(u, v) = map(lambda x: int(x) - 1, input().split())
		adyacentes[u].append((v, i))
	color = [0] * n
	solucion = [1] * m
	c = False
	for r in range(0, n):
		if color[r] == 0:
			c = DFS(r, color, adyacentes, solucion) or c
	print(2 if c else 1)
	print(*solucion, sep=' ')
ColoringEdges()