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

Difficulty: interview

Starter code:

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






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
            else:
                if 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")
    

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 = [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]))

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


import math
# import sys
# input = sys.stdin.readline
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)))

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



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)
        else:
            if 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 = ' ')







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
            else:
                if 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  = 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 = 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))


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

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

# Kahnのアルゴリズム

EDGEIN=[0]*(n+1)# その点に入るEDGEの個数
EDGEOUTLIST=[[] for i in range(n+1)]# EDGEの行き先
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)# 行き先のない点をQUEに入れる



TOP_SORT=[]
while QUE:
    x=QUE.pop()
    TOP_SORT.append(x)# 行き先がない点を答えに入れる
    for to in EDGEOUTLIST[x]:
        EDGEIN[to]-=1# 行き先がない点を削除し,そこから一歩先の点のEDGEINを一つ減らす.
        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=" ")


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

# Kahnのアルゴリズム

EDGEIN=[0]*(n+1)# その点に入るEDGEの個数
EDGEOUTLIST=[[] for i in range(n+1)]# EDGEの行き先
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)# 行き先のない点をQUEに入れる



TOP_SORT=[]
while QUE:
    x=QUE.pop()
    TOP_SORT.append(x)# 行き先がない点を答えに入れる
    for to in EDGEOUTLIST[x]:
        EDGEIN[to]-=1# 行き先がない点を削除し,そこから一歩先の点のEDGEINを一つ減らす.
        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=" ")


'''
  Author: Ashraful Islam Fuad
  University of Asia Pacific
  Bsc in CSE
  category:DFS (dificulty 2000)
  problem :from codeforces 
sd
'''
from collections  import defaultdict

ans=defaultdict(lambda :1)

flag=0


def dfs(node):
	nonlocal flag
	visit[node]=1


	for j in graph[node]:
		if not visit[j]:
			dfs(j)

		else:
			if 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('i is {}'.format(i))  
	print(ans[i],end=' ')




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 = 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)
        else:
            if 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')

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

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)]
#print(adj)
for _ in range(m):
    a,b=list(map(int,input().split()))
    adj[a-1].append([b-1,1,_])
    #print(adj)
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]:
      #  print(j[2],j[1])
        ans[j[2]]=j[1]
print(*ans)
 


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


#!python3

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)]  # adjacency list
def adj(v):
    return al[v]
itoe = [None for _ in range(en)]  # index to edge
for eid in range(en):  # eid - edge id
    v, w = read_int_array()
    v -= 1
    w -= 1
    al[v] += [w]
    itoe[eid] = (v, w)

marked = set()
stack = set()
etoc = {}  # edge to color
def dfs(v):  # vertex
    if v in marked:
        return
    marked.add(v)
    stack.add(v)
    hasbackedge = False
    for w in adj(v):
        if w in stack:  # back edge
            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=' ')







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

# 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):
	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 = [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])

# done = set()
# fnd = set()
# cycle = False
# def dfs(a):
#     for c in chil[a]:
#         print(a,c)
#         if c in fnd:
#             nonlocal cycle
#             cycle = True
#             return
#         if c not in done:
#             fnd.add(c)
#             dfs(c)
# for i in range(1, n+1):
#     if i not in done:
#         dfs(i)
#         done |= fnd
#         fnd = set()
#         if cycle:
#             break

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