D. Coloring Edges

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≤?≤50002≤n≤5000, 1≤?≤50001≤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≤?,?≤?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 ?1,?2,…,??c1,c2,…,cm (1≤??≤?1≤ci≤k), where ??ci 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

Copy

4 5
1 2
1 3
3 4
2 4
1 4

output

Copy

1
1 1 1 1 1 

input

Copy

3 3
1 2
2 3
3 1

output

Copy

2
1 1 2 

 

 

 题解:有向图性质:若有环,则环中必有从编号小的点指向编号大的点,也有编号大的点指向编号小的点.

则若没有环,则都染成1即可,否则只需将从小指向大的边染为1,否则染为2即可.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int maxn=100010;
vector<int>G[maxn];
int flag;
int u[maxn],v[maxn],vis[maxn];
void DFS(int u)
{
  if(flag)return ;
  vis[u]=1;//正在访问
  for(int i=0;i<G[u].size();i++){
    int v=G[u][i];
    if(vis[v]==0)DFS(v);//没访问过
    else if(vis[v]==1){//下一个节点正在访问,即有环
      flag=1;
      return ;
    }
  }
  vis[u]=2;//访问结束
}
int main()
{
  int n,m;
  cin>>n>>m;
  for(int i=1;i<=m;i++){
    cin>>u[i]>>v[i];
    G[u[i]].push_back(v[i]);
  }
  for(int i=1;i<=n;i++){
    if(!vis[i]){
      DFS(i);
    }
  }
  if(!flag){
    cout<<1<<endl;
    for(int i=1;i<=m;i++)cout<<1<<" ";
    cout<<endl;
  }
  else{
    cout<<2<<endl;
    for(int i=1;i<=m;i++){
      if(u[i]<v[i])cout<<1<<" ";
      else cout<<2<<" ";
    }
    cout<<endl;
  }
  return 0;
}