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

struct UnionFind {
    vector<int> par;
    vector<int> rank;
    vector<ll> Size;
    UnionFind(int n = 1) {
        init(n);
    }

    void init(int n = 1) {
        par.resize(n + 1); rank.resize(n + 1); Size.resize(n + 1);
        for (int i = 0; i <= n; ++i) par[i] = i, rank[i] = 0, Size[i] = 1;
    }

    int root(int x) {
        if (par[x] == x) {
            return x;
        }
        else {
            int r = root(par[x]);
            return par[x] = r;
        }
    }

    bool issame(int x, int y) {
        return root(x) == root(y);
    }

    bool merge(int x, int y) {
        x = root(x), y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        Size[x] += Size[y];
        return true;
    }

    ll size(int x) {
        return Size[root(x)];
    }
};
const int INF = 1e9;


struct max_flow {
    struct edge { int to, cap, rev; };
    int V;
    vector<vector<edge>> G;
    vector<int> itr, level;

    max_flow(int V) : V(V) { G.assign(V, vector<edge>()); }

    void add_edge(int from, int to, int cap) {
        G[from].push_back((edge) {to, cap, (int) G[to].size()});
        G[to].push_back((edge) {from, 0, (int) G[from].size() - 1});
    }

    void bfs(int s) {
        level.assign(V, -1);
        queue<int> q;
        level[s] = 0; q.push(s);
        while (!q.empty()) {
            int v = q.front(); q.pop();
            for (auto &e: G[v]) {
                if (e.cap > 0 and level[e.to] < 0) {
                    level[e.to] = level[v] + 1;
                    q.push(e.to);
                }
            }
        }
    }

    int dfs(int v, int t, int f) {
        if (v == t) return f;
        for (int& i = itr[v]; i < (int) G[v].size(); ++i) {
            edge& e = G[v][i];
            if (e.cap > 0 and level[v] < level[e.to]) {
                int d = dfs(e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    int run(int s, int t) {
        int ret = 0, f;
        while (bfs(s), level[t] >= 0) {
            itr.assign(V, 0);
            while ((f = dfs(s, t, INF)) > 0) ret += f;
        }
        return ret;
    }
};

int x[1005], y[1005];

int main() {
    int N, M;
    cin >> N >> M;
    for(int i = 1; i <= M; i++) {
        cin >> x[i] >> y[i];
    }
    UnionFind uni(M + 1);
    for(int i = 1; i <= M; i++) {
        for(int j = i + 1; j <= M; j++) {
            if(x[i] == x[j] || y[i] == y[j]) uni.merge(i, j);
        }
    }
    int mini = 0;
    for(int i = 1; i <= M; i++) {
        if(uni.root(i) == i) mini++;
    }
    //cout << M - mini << endl;
    max_flow graph(2 * N + 10);
    int s = 0;
    int t = 2 * N + 1;
    for(int i = 1; i <= N; i++) {
        graph.add_edge(s, i, 1);
        graph.add_edge(i + N, t, 1);
    }
    for(int i = 1; i <= M; i++) {
        graph.add_edge(x[i], N + y[i], 1);
    }
    int maxi = graph.run(s, t);
    cout << M - maxi << " " << M - mini << endl;
}


Measured memory_bytes: 3328