Educational Codeforces Round 72 D. Coloring Edges（拓扑判环）
题意：现在有n个点，m条有向边，现在要对这m条有向边染色，染色的要求是在一个环里面的边的颜色不能相同，
现在让你求出最少要几种颜色，才能满足条件的染色，并输出方案数
首先判断有无环，没环直接1，
有环的话，设计一种染色方案（差不多是个构造？CF里面好多方案不唯一的都要自己指定一种行之有效的方案出来）
考虑存在环的时候，必然既存在从小点指向大点的边，也存在从大点指向小点的边，对这两种边分别染色就可以保证环内颜色不同，
所以最多只需要两种颜色 
#include <bits/stdc++.h>
using namespace std;
#define endll '\n'
#define C getchar()
typedef long long ll;
#define pi acos(-1.0)
#define INF 0x3f3f3f3f
#define mod 1000000007
#define pii pair<int, int>
const int MAXN = 2e5 + 10;
#define stop system("pause")
#define lowbit(x) ((x) & (-x))
#define Temp template <typename T>
#define mem(a, b) memset(a, b, sizeof(a))
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
Temp inline void rd(T &s)
{
    s = 0;T t = 1, k = C;
    for (; k < '0' || k > '9'; k = C)if (k == '-') t = -1;
    for (; k >= '0' && k <= '9'; k = C) s = (s << 1) + (s << 3) + (k ^ 48);
    s *= t;
}
//
int n,m;
int in[MAXN];
vector<int>mp[MAXN]; 
int topo()
{
    queue<int>q;
    for(int i=1;i<=n;i++)  //n  节点的总数
        if(in[i]==0) q.push(i);  //将入度为0的点入队列
    int k=0;
    while(!q.empty())
    {
        int p=q.front(); q.pop(); // 选一个入度为0的点，出队列
        k++;
        for(int i=0;i<mp[p].size();i++)
        {
            int y=mp[p][i];
            if((--in[y])==0) q.push(y);  
        }
    }
    if(k==n)   return 1;//无环
    else return 0;//  ans 中的长度与n不相等，就说明无拓扑序列，有环
}

char ans[MAXN];
int main()
{
    rd(n),rd(m);
    for(int i=0;i<m;++i)
    {
        int u,v;rd(u),rd(v);
        mp[u].push_back(v);
        in[v]++;
        if(u<v) ans[i]='1';
        else ans[i]='2';
    }
    if(topo())
    {
        printf("1\n");
        for(int i=0;i<m;++i) printf("1 ");
        cout<<endll;
    }
    else
    {
        printf("2\n");
        for(int i=0;i<m;++i) printf("%c ",ans[i]);
        cout<<endll;
    }
    //stop;
    return 0;
}