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;
}