Educational Codeforces Round 72 (Rated for Div. 2)D（DFS，思维）

#define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
int n,m,k=1;
int c[5007],vis[5007];
vector<int>v[5007],no[5007];
void dfs(int u){
vis[u]=-1;
for(int i=0;i<v[u].size();++i){
int t=v[u][i];
int x=no[u][i];
if(vis[t]==-1){//反向边用另一种颜色染
k=2;
c[x]=2;
}
else if(!vis[t])
dfs(t);
}
vis[u]=1;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;++i){
int x,y;
cin>>x>>y;
v[x].push_back(y);
no[x].push_back(i);
}
for(int i=1;i<=n;++i)
if(!vis[i])
dfs(i);
cout<<k<<" ";
for(int i=1;i<=m;++i)
if(c[i]==2)
cout<<2<<" ";
else
cout<<1<<" ";
return 0;
}