#include <bits/stdc++.h>
#define fi first
#define se second
#define inf (long long)1e8
using namespace std;
using p = pair<long long,long long>;

struct Unionfind{
    vector<int> par;
    vector<int> treerank;
    Unionfind(int n = 1){stree(n+1);}
    void stree(int n = 1){
        par.assign(n,-1);
        treerank.assign(n,0);
    }
    int root(int x){
        if(par[x] < 0)return x;
        return par[x] = root(par[x]);
    }
    bool issame(int x,int y){return root(x) == root(y);}
    bool uni(int x,int y){
        x = root(x);
        y = root(y);
        if(x == y)return 0;
        if(treerank[x] > treerank[y])swap(x,y);
        if(treerank[x] == treerank[y])++treerank[y];
        par[y] -= size(x);
        par[x] = y;
        return 1;
    }
    int size(int x){return -par[root(x)];}
};

template<class T>
struct Dinic{
    struct edge{
        int to;
        T cap;
        int rev;
    };
    vector<vector<edge>> lst;
    vector<int> completed;
    vector<int> dist;
    Dinic(int n = 1){
        lst.resize(n);
        completed.resize(n);
        dist.resize(n);
    }
    bool add(int start,int goal,T capacity){
        lst[start].push_back((edge){goal,capacity,(int)lst[goal].size()});
        lst[goal].push_back((edge{start,0,(int)lst[start].size()-1}));
        return 1;
    }
    void distbfs(int start){
        fill(dist.begin(),dist.end(),-1);
        queue<int> bfsqu;
        dist[start] = 0;
        bfsqu.push(start);
        while(bfsqu.size() > 0){
            int now = bfsqu.front();
            bfsqu.pop();
            for(int i=0;i < lst[now].size();++i){
                edge* nowe = &lst[now][i];
                if(nowe->cap > 0 && dist[nowe->to]<0){
                    dist[nowe->to] = dist[now] + 1;
                    bfsqu.push(nowe->to);
                }
            }
        }
    }
    T pathdfs(int now,int goal,T nf){
        if(now == goal)return nf;
        for(int& i= completed[now];i < lst[now].size();++i){
            edge* e = &lst[now][i];
            if(e->cap > 0 && dist[now] < dist[e->to]){
                T ans = pathdfs(e->to,goal,min(nf,e->cap));
                if(ans > 0){
                    e->cap -= ans;
                    lst[e->to][e->rev].cap += ans;
                    return ans;
                }
            }
        }
        return 0;
    }
    T solve(int start,int goal){
        T ans=0,nf = 0;
        while(1){
            distbfs(start);
            if(dist[goal]<0)return ans;
            fill(completed.begin(),completed.end(),0);
            while((nf=pathdfs(start,goal,inf))>0)ans += nf;
        }
        return -1;
    }
};

long long n,m;
long long dp[1005][1005][2][2] = {0};
vector<long long> lstx[1005],lsty[1005];
vector<p> v;
Unionfind uf;
set<p> st;

long long solve();

int main() {
    cin >> n >> m;
    v.resize(m);
    for (int i = 0; i < m; ++i){
        cin >> v[i].fi >> v[i].se;
        --v[i].fi;
        --v[i].se;
        st.insert(v[i]);
    }
    cout << solve() << endl;
    return 0;
}

long long solve(){
    long long ans = 0;
    uf = Unionfind(m);
    sort(v.begin(),v.end());
    for(int i = 0;i < m;++i){
        lstx[v[i].fi].push_back(i);
        lsty[v[i].se].push_back(i);
    }
    for(int i=0;i<n;++i){
        for(int j=1;j<lstx[i].size();++j)
            uf.uni(lstx[i][j],lstx[i][j-1]);
        for(int j=1;j<lsty[i].size();++j)
            uf.uni(lsty[i][j],lsty[i][j-1]);
    }
    //min
    Dinic<int> din(2 * n +2);
    for(int i = 0;i < m;++i)
        din.add(v[i].fi,v[i].se + n,1);
    for(int i = 0;i < n;++i){
        din.add(2 * n,i,1);
        din.add(i + n,2 * n + 1,1);
    }
    cout << m - din.solve(2 * n,2 * n+1)<< " ";
    // max
    ans = 0;
    vector<bool> ch(m,0);
    for(int i = 0;i < m;++i)
        if(!ch[uf.root(i)]) {
            ans += uf.size(uf.root(i)) - 1;
            ch[uf.root(i)] = 1;
        }
    return ans;
}


Measured memory_bytes: 3500