educational codeforces round 72 d. coloring edges（拓扑判环）

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 (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("1n");
        for(int i=0;i<m;++i) printf("1 ");
        cout<<endll;
    }
    else
    {
        printf("2n");
        for(int i=0;i<m;++i) printf("%c ",ans[i]);
        cout<<endll;
    }
    //stop;
    return 0;
}