Au Revoir, icpc

#include <bits/stdc++.h>
#include <bits/extc++.h>

using ll = long long;
using namespace __gnu_pbds;

template <class T> using splay =
    tree<T, null_type, std::less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T> using splay2 =
    tree<T, null_type, std::greater<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n, m;
    std::cin >> n >> m;

    int cnt = n * m;
    std::vector<std::string> mp(n);
    for (auto &i : mp)
        std::cin >> i, cnt -= std::count(i.begin(), i.end(), '0');

    //     std::cout << "! " << cnt << '\n';

    auto get = [&](int x, int y) {
        return x * m + y;
    };
    std::vector<int> vis(n * m);

    std::vector<std::pair<int, int>> dir = {
        {1, 0}, {0, 1}, {-1, 0}, {0, -1},
    };

    std::function<void(int, int)> dfs = [&](int i, int j) {
        if (vis[get(i, j)]) return;
        vis[get(i, j)] = 1;
        for (auto [dx, dy] : dir) {
            int px = i + dx;
            int py = j + dy;
            if (px < 0 || px >= n || py < 0 || py >= m) continue;
            if (vis[get(px, py)]) continue;
            if (mp[px][py] != '0') {
                mp[px][py] = mp[i][j];
                dfs(px, py);
            }
        }
    };


    std::function<void(int, int)> dfs2 = [&](int i, int j) {
        if (vis[get(i, j)]) return;
        vis[get(i, j)] = 1;
        for (auto [dx, dy] : dir) {
            int px = i + dx;
            int py = j + dy;
            if (px < 0 || px >= n || py < 0 || py >= m) continue;
            if (vis[get(px, py)]) continue;
            if (mp[px][py] != '0') {
                mp[px][py] = '2';
                dfs2(px, py);
            }
        }
    };

    auto counter = [&]() {
        static char c = '1';
        int ans = cnt;

        std::vector<int> p(n * m);
        std::iota(p.begin(), p.end(), 0);
        std::function<int(int)> find = [&](int x) -> int {
            return p[x] = p[x] == x ? x : find(p[x]);
        };
        auto merge = [&](int i, int j, int x, int y) {
            int X = find(get(i, j));
            int Y = find(get(x, y));
            if (X == Y) return 0;
            return p[X] = Y, 1;
        };

        using pii = std::pair<int, int>;

        std::queue<pii> q;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mp[i][j] == c)
                    q.emplace(i, j);
            }
        }

        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            if (vis[get(x, y)]) continue;
            vis[get(x, y)] = 1;
            for (auto [dx, dy] : dir) {
                int px = dx + x, py = dy + y;
                if (px < 0 || px >= n || py < 0 || py >= m) continue;
                if (mp[px][py] == c) {
                    ans -= merge(x, y, px, py);
                    q.emplace(px, py);
                    vis[get(px, py)] = 1;
                }
            }
        }

        c ++;
        return ans - 1;
    };

    auto restore = mp;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (mp[i][j] == '1')
                dfs(i, j);
        }
    }

    vis =  std::vector<int>(n * m);
    std::cout << counter() << ' ';

    vis =  std::vector<int>(n * m);
    mp = restore;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (mp[i][j] >= '2')
                mp[i][j] = '2';
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (mp[i][j] == '2')
                dfs2(i, j);
        }
    }


    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (mp[i][j] == '1') {
                mp[i][j] = '0';
                cnt -= 1;
            }
        }
    }

//    for (auto &i : mp) std::cout << i << '\n';

    vis =  std::vector<int>(n * m);
    std::cout << counter() << '\n';

    return 0;
}