Educational Codeforces Round 72 (Rated for Div. 2) 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≤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 c1,c2,…,cm (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，序号大的點指向序号小的點染2，那麼這個環一定有兩種顔色，是以，我們隻要用拓撲排序判圖中有沒有環，沒有直接輸出1，有輸出2

#include<stdio.h>
    #include<math.h>
    #include<vector>
    #include<cstring>
    #include<queue>
    #include<iostream>
    #include<algorithm>
    #define maxn 15000
    using namespace std;
    #define ll long long
    int in[maxn],n,m,ans[maxn],head[maxn],cnt;
    struct Edge
    {
        int to,next;
    } edge[maxn];
    void addedge(int u,int v)
    {
        edge[cnt].to=v;
        edge[cnt].next=head[u];
        head[u]=cnt++;
        in[v]++;
    }
    void init()
    {
        memset(in,0,sizeof(in));
        memset(head,-1,sizeof(head));
        cnt=0;
    }
    int slove()
    {
        queue<int>q;
        for(int i=1; i<=n; i++)
        {
            if(in[i]==0)
                q.push(i);
        }
        int sum=n;
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            sum--;
            for(int i=head[u]; i!=-1; i=edge[i].next)
            {
                int v=edge[i].to;
                in[v]--;
                if(in[v]==0)
                    q.push(v);
            }
        }
        if(sum==0)
            return 1;
        else
            return 2;
    }
    int main()
    {
        init();
        scanf("%d %d",&n,&m);
        for(int i=1; i<=m; i++)
        {
            int u,v;
            scanf("%d %d",&u,&v);
            if(u>v)
                ans[i]=1;
            else
                ans[i]=2;
            addedge(u,v);
        }
        int k=slove();
        printf("%d\n",k);
        if(k==1)
        {
            for(int i=1; i<=m; i++)
            {
                if(i==m)
                    printf("1\n");
                else
                    printf("1 ");
            }
            return 0;
        }
     
        for(int i=1; i<=m; i++)
        {
            if(i==m)
                printf("%d\n",ans[i]);
            else
                printf("%d ",ans[i]);
        }
    }