HA33_SCC(16)

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

class Graph {
private:
    int N;
    int M;
    vector<vector<int>> adj;
public:
    Graph(int n, int m) : N(n), M(m), adj(n + 1) {}
    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }
    Graph getTranspose() const {
        Graph transposed(N, M);
        for (int u = 1; u <= N; ++u) {
            for (int v : adj[u]) {
                transposed.addEdge(v, u);
            }
        }
        return transposed;
    }
    int getN() const { return N; }
    const vector<vector<int>>& getAdj() const { return adj; }
    void dfs(int u, stack<int>& finishStack, vector<bool>& visited) const {
        visited[u] = true;
        for (int v : adj[u]) {
            if (!visited[v]) {
                dfs(v, finishStack, visited);
            }
        }
        finishStack.push(u);
    }
};

class StronglyConnectedComponents {
private:
    const Graph& graph;
    Graph transposeGraph;
    vector<int> component;
    stack<int> finishStack;
    int numberOfComponents;
public:
    StronglyConnectedComponents(const Graph& g)
        : graph(g), transposeGraph(g.getTranspose()), component(g.getN() + 1, 0), numberOfComponents(0) {}
    void findSCCs() {
        // Первый DFS на исходном графике для заполнения конечного стека
        vector<bool> visited(graph.getN() + 1, false);
        for (int u = 1; u <= graph.getN(); ++u) {
            if (!visited[u]) {
                graph.dfs(u, finishStack, visited);
            }
        }

        // Второй DFS на графике транспонирования в порядке завершения стека
        vector<bool> visited2(transposeGraph.getN() + 1, false);
        while (!finishStack.empty()) {
            int u = finishStack.top();
            finishStack.pop();
            if (!visited2[u]) {
                numberOfComponents++;
                // Присваиваем номер компоненты с помощью итеративного DFS
                stack<int> dfsStack;
                dfsStack.push(u);
                visited2[u] = true;
                component[u] = numberOfComponents;
                while (!dfsStack.empty()) {
                    int current = dfsStack.top();
                    dfsStack.pop();
                    for (int v : transposeGraph.getAdj()[current]) {
                        if (!visited2[v]) {
                            visited2[v] = true;
                            component[v] = numberOfComponents;
                            dfsStack.push(v);
                        }
                    }
                }
            }
        }
    }
    int getComponentCount() const {
        return numberOfComponents;
    }
    vector<int> getComponents() const {
        return component;
    }
};

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

    int N, M;
    cin >> N >> M;

    Graph graph(N, M);
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        graph.addEdge(u, v);
    }

    StronglyConnectedComponents scc(graph);
    scc.findSCCs();
    vector<int> components = scc.getComponents();

    cout << scc.getComponentCount() << endl;
    for (int u = 1; u <= N; ++u) {
        cout << components[u] << " ";
    }
    cout << endl;

    return 0;
}