#include <bits/stdc++.h>

using namespace std;

const int N = 1e3+5;
deque<pair<int, int>> x[N], y[N];
set<int> adj[N], adj2[N];
set<pair<int, int>> X[N], Y[N];
int indeg[N], indeg2[N], R[N], C[N];

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m; cin >> n >> m;
    for(int i=0; i<m; i++){
        int a, b; cin >> a >> b;
        R[i] = a;
        C[i] = b;
        x[a].push_back({b, i});
        y[b].push_back({a, i});
        X[a].insert({b, i});
        Y[b].insert({a, i});
    }
    for(auto &h : x){
        sort(h.begin(), h.end());
    }
    for(auto &h : y){
        sort(h.begin(), h.end());
    }
    for(auto &h : x){
        for(int i=0; i<(int)h.size()-1; i++){
            indeg[h[i].second]++;
            indeg[h[i+1].second]++;
            adj[h[i].second].insert(h[i+1].second);
            adj[h[i+1].second].insert(h[i].second);
        }
    }
    for(auto &h : y){
        for(int i=0; i<(int)h.size()-1; i++){
            indeg[h[i].second]++;
            indeg[h[i+1].second]++;
            adj[h[i].second].insert(h[i+1].second);
            adj[h[i+1].second].insert(h[i].second);
        }
    }

    // for(int i=0; i<N; i++){
    //     if(adj[i].empty())continue;
    //     auto x = adj[i];
    //     for(auto y : x){
    //         cout << y << " " << i << '\n';
    //     }
    // }

    int ans1 = 0, ans2 = 0;
    set<pair<int, int>> st;
    for(int i=0; i<n; i++){
        if(indeg[i] == 0)continue;
        st.insert({indeg[i], i});
    }
    for(int i=0; i<N; i++)indeg2[i] = indeg[i], adj2[i] = adj[i];
    while(st.size()){
        int u = st.rbegin() -> second;
        st.erase({indeg[u], u});
        ans1++;
        if(X[R[u]].begin()->second == u){
            auto nxt = X[R[u]].begin();
            nxt++;
            int v = nxt->second;
            st.erase({indeg[v], v});
            indeg[v]--;
            if(indeg[v] > 0)
                st.insert({indeg[v], v});
        } else if(X[R[u]].rbegin()->second == u){
            auto prev = X[R[u]].rbegin();
            prev++;
            int v = prev->second;
            st.erase({indeg[v], v});
            indeg[v]--;
            if(indeg[v] > 0)
                st.insert({indeg[v], v});
        } 
        if(Y[C[u]].begin()->second == u){
            auto nxt = Y[C[u]].begin();
            nxt++;
            int v = nxt->second;
            st.erase({indeg[v], v});
            indeg[v]--;
            if(indeg[v] > 0)
                st.insert({indeg[v], v});
        } else if(Y[C[u]].rbegin()->second == u){
            auto prev = Y[C[u]].rbegin();
            prev++;
            int v = prev->second;
            st.erase({indeg[v], v});
            indeg[v]--;
            if(indeg[v] > 0)
                st.insert({indeg[v], v});
        } 
        X[R[u]].erase({C[u], u});
        Y[C[u]].erase({R[u], u});
    }
    while(st.size())st.erase(st.begin());
    for(int i=0; i<N; i++)indeg[i] = indeg2[i], adj[i] = adj2[i];
    for(int i=0; i<n; i++){
        if(indeg[i] == 0)continue;
        st.insert({indeg[i], i});
    }
    
    while(st.size()){
        int u = st.begin() -> second;
        st.erase({indeg[u], u});
        ans2++;
        for(auto v : adj[u]){
            st.erase({indeg[v], v});
            indeg[v]--;
            if(indeg[v])
                st.insert({indeg[v], v});
            adj[v].erase(u);
        }
    }
    cout << ans1 << " " << ans2 << endl;

}