codeforces 1217d D. Coloring Edges

题意：一个有向图，染色，环的边不能只有1个颜色。问需几种颜色及染色方案。

最多2种颜色。无环时1种，有环时2种。用dfs判环，类似tarjan,还在栈中的点又被访问就有环。backedge染2，其他染1.简化一下。如果有环ai<bi的边染1，ai>bi的边染2。正确性似乎正确。

//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cstring>
#include <map>
#include <queue>
#include <set>
#include <cassert>
#include <stack>
#include <bitset>
#include <unordered_set>
#define mkp make_pair
using namespace std;
const double EPS=1e-8;
typedef long long lon;
typedef pair<lon,lon> pii ;
const lon SZ=100010,SSZ=0,APB=26,INF=0x7FFFFFF,mod=1000000007;
lon n,m;
vector<int> mp[SZ];
pii in[SZ];
bool vst[SZ],ok,inq[SZ];

void dfs(int x,int p)
{
    vst[x]=1;
    inq[x]=1;
    for(int i=0;i<mp[x].size();++i)
    {
        int to=mp[x][i];
        //if(to!=p)
        //{
            if(inq[to])ok=1;
            else if(!vst[to])dfs(to,x);
        //}
    }
    inq[x]=0;
}
 
void init()
{
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int u,v;
        cin>>u>>v;
        mp[u].push_back(v);
        in[i]=mkp(u,v);
    }
    for(int i=1;i<=n;++i)
    if(!vst[i])dfs(i,-1);
    if(ok)
    {
        cout<<2<<endl;
        for(int i=1;i<=m;++i)
        {
            if(i!=1)cout<<" ";
            cout<<(in[i].first<in[i].second?1:2);
        }
        cout<<endl;
    }
    else
    {
        cout<<1<<endl;
        for(int i=1;i<=m;++i)
        {
            if(i!=1)cout<<" ";
            cout<<1;
        }
        cout<<endl;
    }
}
 
void work()
{
    
}
 
int main()
{
    std::ios::sync_with_stdio(0);
    //freopen("d:\\1.txt","r",stdin);
    //lon casenum;
    //cin>>casenum;
    //for(lon tim=1;tim<=casenum;++tim)
    {
        init();
        work();
    }
    return 0;
}