本文共 2510 字，大约阅读时间需要 8 分钟。

You are given a directed graph with nn vertices and mm directed edges without self-loops or multiple edges.

Let’s denote the kk-coloring of a digraph as following: you color each edge in one of kk colors. The kk-coloring is good if and only if there no cycle formed by edges of same color.

Find a good kk-coloring of given digraph with minimum possible kk.

Input

The first line contains two integers nn and mm (2≤n≤50002≤n≤5000, 1≤m≤50001≤m≤5000) — the number of vertices and edges in the digraph, respectively.

Next mm lines contain description of edges — one per line. Each edge is a pair of integers uu and vv (1≤u,v≤n1≤u,v≤n, u≠vu≠v) — there is directed edge from uu to vv in the graph.

It is guaranteed that each ordered pair (u,v)(u,v) appears in the list of edges at most once.

Output

In the first line print single integer kk — the number of used colors in a good kk-coloring of given graph.

In the second line print mm integers c1,c2,…,cmc1,c2,…,cm (1≤ci≤k1≤ci≤k), where cici is a color of the ii-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 kk).

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 题意：给图中的边染色，相同颜色的边不能组成环。问最少几种颜色可以染色成功。 有向图判断有没有环，首先想到的就是拓扑排序。如果这个图没有环，这样的环，那么只用一种颜色就可以实现题目要求。如果有环的话，有两种颜色就够了。 我这个题瓶颈是两种情况的时候，输出应该怎么输出。试了好多都不对。后来看了看题解，输出的时候，如果u>v，就输出1。否则就输出2，这样的话一个环中一定不会有相同颜色。 代码如下：

#include
   
    #include
    
     #define ll long long#define random(a, b) ((a) + rand() % ((b) - (a) + 1))using namespace std;const int maxx=5e3+100;struct edge{
   	int to,next;}e[maxx<<1];struct node{
   	int x,y;}pp[maxx];int head[maxx<<1];int in[maxx];int vis[maxx];int cor[maxx];int n,m,tot;map
     
      
       ,int> mp;/*----------事前准备-----------*/inline void init(){
   	memset(head,-1,sizeof(head));	tot=0;}inline void add(int u,int v){
   	e[tot].to=v,e[tot].next=head[u],head[u]=tot++;}int main(){
   	int x,y;	scanf("%d%d",&n,&m);	init();	for(int i=1;i<=m;i++)	{
   		scanf("%d%d",&x,&y);		pp[i].x=x,pp[i].y=y;		add(x,y);		in[y]++;	}	queue
       
         p;	for(int i=1;i<=n;i++) if(in[i]==0) p.push(i);	while(p.size())	{
   		int x=p.front();		p.pop();		vis[x]=1;		for(int i=head[x];i!=-1;i=e[i].next)		{
   			int to=e[i].to;			in[to]--;			if(in[to]==0) p.push(to);		}	}	int flag=1;	for(int i=1;i<=n;i++) if(!vis[i]) flag=0;	if(flag)	{
   		cout<<1<
        
         pp[i].y) cout<<1<<" "; else cout<<2<<" "; } cout<
        
       
      
     
    
   

努力加油a啊，(^o)/~

转载地址：http://uftvi.baihongyu.com/