#include <bits/stdc++.h>
using namespace std;

/*
 Tarjan 强连通分量 (SCC) 单次 DFS 实现（0-indexed）
 - 输入图为邻接表 g (n nodes)
 - 输出：
    int scc_cnt               : 强连通分量个数
    vector<int> comp(n)       : 每个节点所属的 SCC id（0..scc_cnt-1）
    vector<vector<int>> groups: 若需要每个组件的节点列表（可选）
 时间复杂度: O(n + m)
 适用场景: 竞赛、图论题
*/

struct TarjanSCC {
    int n;
    vector<vector<int>> g;

    // 维护项
    vector<int> dfn;     // dfn[v] = 发现时间（从1开始），0 表示未访问
    vector<int> low;     // low-link 值
    vector<char> in_stack; // 是否在栈中
    vector<int> stk;     // 模拟栈（也可用 vector<int> 的 push_back/pop_back）
    int timer;
    int scc_cnt;
    vector<int> comp;    // comp[v] = scc id (0..scc_cnt-1)
    vector<vector<int>> groups; // 各 scc 的节点列表 (可选)

    TarjanSCC(int n = 0) { init(n); }

    void init(int n_) {
        n = n_;
        g.assign(n, {});
        dfn.assign(n, 0);
        low.assign(n, 0);
        in_stack.assign(n, 0);
        stk.clear();
        timer = 0;
        scc_cnt = 0;
        comp.assign(n, -1);
        groups.clear();
    }

    void add_edge(int u, int v) {
        g[u].push_back(v);
    }

    // Tarjan DFS from vertex v
    void dfs(int v) {
        dfn[v] = low[v] = ++timer; // 发现时间
        stk.push_back(v);
        in_stack[v] = 1;

        for (int to : g[v]) {
            if (dfn[to] == 0) {
                // tree-edge
                dfs(to);
                low[v] = min(low[v], low[to]);
            } else if (in_stack[to]) {
                // back-edge / cross-edge to a node still in current stack: can update low
                low[v] = min(low[v], dfn[to]);
            }
            // 若 to 已被分派到某个 SCC（in_stack[to]==0 且 dfn[to]>0），则不能用来更新 low[v]
            // 因为该节点已从栈中弹出并已归属某个 SCC（与当前 v 的 SCC 不再相关）
        }

        // v 是 SCC 根：把栈中元素弹出直到 v，组成一个 SCC
        if (low[v] == dfn[v]) {
            // 新的 SCC：编号为 scc_cnt
            groups.emplace_back();
            while (true) {
                int x = stk.back();
                stk.pop_back();
                in_stack[x] = 0;
                comp[x] = scc_cnt;
                groups.back().push_back(x);
                if (x == v) break;
            }
            ++scc_cnt;
        }
    }

    // 运行 Tarjan，返回 scc 数，并填充 comp/groups
    int run() {
        // reset timer & results in case run() 被多次调用
        timer = 0;
        scc_cnt = 0;
        fill(dfn.begin(), dfn.end(), 0);
        fill(low.begin(), low.end(), 0);
        fill(in_stack.begin(), in_stack.end(), 0);
        stk.clear();
        comp.assign(n, -1);
        groups.clear();

        for (int v = 0; v < n; ++v) {
            if (dfn[v] == 0) dfs(v);
        }
        return scc_cnt;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    TarjanSCC scc(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        // 假设输入为 0-indexed；若为 1-indexed，请在这里做 --u; --v;
        // --u; --v;
        scc.add_edge(u, v);
    }

    int cnt = scc.run();
    // 输出：SCC 个数，和每个节点所属的 comp id
    cout << "SCC count: " << cnt << '\n';
    // comp id 范围 0..cnt-1（Tarjan 的生成顺序：根被发现时分配 0,1,...）
    for (int v = 0; v < n; ++v) {
        cout << scc.comp[v] << (v + 1 == n ? '\n' : ' ');
    }

    // 若想要缩点图的拓扑序：注意 Tarjan 分配的 id 不是缩点图的拓扑序（通常是逆拓扑或任意顺序）
    // 若需要拓扑（从源到汇的顺序），可以构建缩点图并对其做拓扑排序。

    return 0;
}