#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 1001 , MOD =  998244353 ; //1e9 + 7;

template <bool ToShuffle = false>
struct bipartite_matching {
    int n_left, n_right, flow = 0;
    std::vector<std::vector<int>> g;
    std::vector<int> match_from_left, match_from_right;

    bipartite_matching(int _n_left, int _n_right)
            : n_left(_n_left),
              n_right(_n_right),
              g(_n_left),
              match_from_left(_n_left, -1),
              match_from_right(_n_right, -1),
              dist(_n_left) {}

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

    std::vector<int> dist;

    void bfs() {
        std::queue<int> q;
        for (int u = 0; u < n_left; ++u) {
            if (!~match_from_left[u])
                q.push(u), dist[u] = 0;
            else
                dist[u] = -1;
        }
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto v : g[u])
                if (~match_from_right[v] && !~dist[match_from_right[v]]) {
                    dist[match_from_right[v]] = dist[u] + 1;
                    q.push(match_from_right[v]);
                }
        }
    }

    bool dfs(int u) {
        for (auto v : g[u])
            if (!~match_from_right[v]) {
                match_from_left[u] = v, match_from_right[v] = u;
                return true;
            }
        for (auto v : g[u])
            if (dist[match_from_right[v]] == dist[u] + 1 &&
                dfs(match_from_right[v])) {
                match_from_left[u] = v, match_from_right[v] = u;
                return true;
            }
        return false;
    }

    int get_max_matching() {
        if constexpr (ToShuffle) {

            for (int i = 0; i < n_left; ++i)
                std::random_shuffle(std::begin(g[i]), std::end(g[i]));
        }
        while (true) {
            bfs();
            int augment = 0;
            for (int u = 0; u < n_left; ++u)
                if (!~match_from_left[u]) augment += dfs(u);
            if (!augment) break;
            flow += augment;
        }
        return flow;
    }

    std::pair<std::vector<int>, std::vector<int>> minimum_vertex_cover() { //vertex cover max mat = x.sz + y.sz
        std::vector<int> L, R;
        for (int u = 0; u < n_left; ++u) {
            if (!~dist[u])
                L.push_back(u);
            else if (~match_from_left[u])
                R.push_back(match_from_left[u]);
        }
        return {L, R};
    }

    std::vector<std::pair<int, int>> get_edges() {
        std::vector<std::pair<int, int>> ans;
        for (int u = 0; u < n_left; ++u)
            if (match_from_left[u] != -1)
                ans.emplace_back(u, match_from_left[u]);
        return ans;
    }
};

int n , ex[N][N];

struct union_find {
    int comps;
    vector<int> parent, length;
    union_find(int n) {
        comps = n;
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);
        length = vector<int>(n, 1);
    }
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    void unite(int x, int y) {
        int Px = find(x);
        int Py = find(y);
        if (Px == Py) { return; }
        comps--;
        if (length[Px] < length[Py]) {
            swap(Px, Py);
        }
        parent[Py] = Px;
        length[Px] += length[Py];
    }
};

int x[N] , y[N];
int max_ans() {
    union_find dsu(n);
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (x[i] == x[j] || y[i] == y[j]) {
                dsu.unite(i, j);
            }
        }
    }
    return n - dsu.comps;
}

int32_t main() {

    cin.tie(0);cin.sync_with_stdio(0);
    cout.tie(0);cout.sync_with_stdio(0);

    int d ;
    cin >> d >> n;

    for(int i= 0 ; i < n; i++)
    {
        cin >> x[i] >> y[i] ;

        ex[ x[i] - 1 ][ y[i] - 1 ] = 1;
    }

    bipartite_matching<0> mat(d , d );

    for(int i= 0 ;i < d ; i++) for(int j =0 ; j < d ; j++) if( ex[i][j] ) mat.add(i , j) ;

    cout << n - mat.get_max_matching() << " " << max_ans() ;

    return 0;
}