CF1217D

link

为啥$O(n+m)$只出到5000啊？

dfs，返祖边为2，其它边为1.

考虑一下正确性

首先k=1当且仅当无环，也就是dfs树没返祖边

考虑2是向上的不会出环，

1是向下的和向前面子树的，向下的不会有问题，向前面子树的一定不可能通过向下和向前跳到这个点（否则这条边一定是返祖边），所以就没问题了

vector<int> to[5005];
bool qaq;
int e[5005],vis[5005],ins[5005];
int col[5005],hv;
void dfs(int x){
    vis[x]=1;
    ins[x]=1;
    for(auto i:to[x])if(!vis[e[i]]){
        dfs(e[i]);
    }
    else if(ins[e[i]]){hv=1;col[i]=1;}
    ins[x]=0;
}
signed main(){
#ifdef QAQAutoMaton 
    freopen("D.in","r",stdin);
    freopen("D.out","w",stdout);
#endif
    int n,m,u,v;
    read(n,m);
    qaq=1;
    for(int i=1;i<=m;++i){
        read(u,v);
        to[u].push_back(i);
        e[i]=v;
    }
    for(int i=1;i<=n;++i)if(!vis[i]){
        dfs(i);
    }
    write(hv+1,'\n');
    for(int i=1;i<=m;++i)write(col[i]+1,i==m?'\n':' ');
    return 0;
}