Nếu ~m = 0~, thì số màu ít nhất cần sử dụng là ~0~.

Nếu đồ thị không có chu trình, thì số màu ít nhất cần sử dụng là ~1~.

Nếu đồ thị có chu trình, thì ta thấy cần sử dụng nhiều hơn ~1~ màu, ta có cách tô sử dụng ~2~ màu như sau: Xét cung ~(u, v)~ - Nếu ~u < v~ thì tô màu số hiệu ~1~. - Nếu ~u > v~ thì tô màu số hiệu ~2~.

Ở hai trường hợp đầu tiên, ta dễ dàng thấy nó đúng. Còn ở trường hợp thứ ba ta thấy rằng: Xét từng chu trình trong đồ thị có dạng: ~x_1, x_2, \dots, x_k, x_{k+1} = x_1~, luôn tồn tại vị trí ~h~ có ~x_{h-1} < x_h > x_{h+1}~ thì chu trình đang xét sẽ được tô hai màu. Màu ~1~ ở cung ~(x_{h-1}, x_h)~ và màu ~2~ ở cung ~(x_{h}, x_{h + 1})~.

Code mẫu

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 7;

vector <int> adj[MAXN];
pair <int, int> e[MAXN];
int n, m, d[MAXN];
bool cycle = 0;

void DFS(int u)
{
    if (cycle) return;
    d[u] = 1;
    for (auto v: adj[u])
        if (!d[v]) DFS(v);
        else if (d[v] == 1) cycle = 1;
    d[u] = 2;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    if (m == 0) return cout << 0, 0;

    for (int i = 1; i <= m; ++i) 
    {
        cin >> e[i].first >> e[i].second;
        adj[e[i].first].push_back(e[i].second);
    }

    for (int i = 1; i <= n; ++i)
        if (!d[i]) DFS(i);

    cout << cycle + 1 << '\n';
    for (int i = 1; i <= m; ++i)
        if (e[i].first < e[i].second)
            cout << "1\n";
        else 
            cout << 1 + cycle << '\n';

    return 0;
}