#include <bits/stdc++.h>
#define REP(i,n) for (long long i=0;i<(n);i++)
#define FOR(i,a,b) for (long long i=(a);i<(b);i++)
#define dump(x)  cerr << #x << " => " << (x) << endl
#define MIN(vec) *min_element(vec.begin(), vec.end())
#define MAX(vec) *max_element(vec.begin(), vec.end())
#define UNIQ(vec) vec.erase(unique(vec.begin(), vec.end()),vec.end()) //ソートの必要あり
#define IN(n,m)  (!(m.find(n) == m.end()))
#define FINDL(vec,x) (lower_bound(vec.begin(),vec.end(),x) - vec.begin())
#define FINDU(vec,x) (upper_bound(vec.begin(),vec.end(),x) - vec.begin())
#define EQ(a,b) (abs(a - b) < 1e-10)
using namespace std;
typedef long long LL;
constexpr int dx[4] = {0,1,0,-1};
constexpr int dy[4] = {1,0,-1,0};
constexpr long double pi = M_PI;
constexpr double eps = 1e-10;
constexpr long mod = 1000000007;
// LONG_MAX,LLONG_MAX
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class Key,class Value> ostream& operator << (ostream &s, map<Key,Value> M)
{ for ( auto itr = begin(M); itr != end(M); ++itr) { s << itr->first << ":" << itr->second; } return s;}


using Long = long long;

struct UnionFind {
    int n;
    vector<int> sz,par;
    UnionFind(){}
    UnionFind(int sz):n(sz),sz(sz,1),par(sz,0){ iota(par.begin(),par.end(),0); }
    // xの親を見つける.
    int find(int x){
        return (x==par[x]?x:par[x]=find(par[x]));
    }
    // 同じ集合か
    bool same(int x,int y){
        return find(x)==find(y);
    }
    // xの属する集合とyの属する集合を結合
    void unite(int x,int y){
        x=find(x);y=find(y);
        if(x==y) return;
        if(sz[x]<sz[y]) swap(x,y);
        sz[x]+=sz[y];
        par[y]=x;
    }
    // xの属する集合サイズ
    int size(int x){
        return sz[find(x)];
    }
};

/**
 * @brief 逆辺, 容量情報をもつ辺 
 * @param to : 出力先の頂点
 * @param rev : 逆辺のインデックス, from <=> E[to][rev].to
 * @param cap : 辺の容量
 */
template<typename W>
struct Edge { 
    int to,rev;
    W cap;
    Edge(int to, int rev, W cap) : to(to), rev(rev), cap(cap) {}
};

template<typename W>
using Graph = vector<vector<Edge<W>>>;

template<typename W>
struct NetWork {
    Graph<W> G;
    NetWork(int V) : G(V) { }
    /**
     * @brief 最大流問題におけるネットワークの辺を追加.逆辺も同時に追加する.
     */
    void add_edge(int from, int to, W cap) {
        G[from].emplace_back(to, (int)G[to].size(), cap);
        G[to].emplace_back(from, (int)G[from].size()-1, 0);
    }
    size_t size() {
        return G.size();
    }
};

// private
template<typename W>
void bfs(int s, Graph<W> &g, vector<int> &level) {
    fill(level.begin(),level.end(), -1);
    queue<int> que;
    level[s] = 0;
    que.push(s);
    while(!que.empty()) {
        int v=que.front();que.pop();
        for(auto &&e : g[v]) {
            if( e.cap > 0 && level[e.to] < 0) {
                level[e.to] = level[v]+1;
                que.push(e.to);
            }
        }
    }
}

// private
template<typename W>
W dfs(int v,int t,W f, Graph<W> &g, vector<int> &iter, vector<int> &level) {
    if(v==t) return f;
    for(int &i = iter[v] ; i < g[v].size();i++ ) {
        Edge<W> &e = g[v][i];
        if( e.cap > 0 && level[v]<level[e.to] ) {
            int d = dfs(e.to, t , min(f , e.cap), g, iter, level);
            if( d > 0 ) {
                e.cap -= d;
                g[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

// Dinic法
template<typename W>
W max_flow(NetWork<W> &network, int s, int t) {
    W flow = 0;
    // networkのグラフ
    Graph<W> &g = network.G;
    // level[i] : 頂点sから頂点iまでの最短距離
    vector<int> level(g.size(), -1);
    vector<int> iter(g.size(), 0);
    for( ; ; ) {
        bfs(s, g, level);
        // フローを流せるエッジが存在しない.
        if( level[t] < 0 ) return flow;
        fill(iter.begin(),iter.end(),0);
        int f;
        while( (f=dfs(s , t, numeric_limits<W>::max(), g, iter, level)) > 0){
            flow += f;
        }
    }
    return flow;
}

// 二部グラフ.
struct BipartiteGraph : NetWork<int> {
    set<int> setX, setY;
    BipartiteGraph(int V) : NetWork<int>::NetWork(V+2) { }
    BipartiteGraph(set<int> &setX, set<int> &setY): 
        NetWork<int>::NetWork(setX.size() + setY.size()+2),setX(setX), setY(setY) {
        int V = setX.size() + setY.size() + 2;
        for(auto &&x : setX)
            NetWork<int>::add_edge(V-2, x, 1);
        for(auto &&y : setY)
            NetWork<int>::add_edge(y, V-1, 1);
    }

    void add_edge(int x, int y) {
        NetWork<int>::add_edge(x, y, 1);
        if (!setX.count(x)) {
            NetWork<int>::add_edge(NetWork<int>::G.size()-2, x, 1);
            setX.insert(x);
        }
        if (!setY.count(y)) {
            NetWork<int>::add_edge(y, NetWork<int>::G.size()-1, 1);
            setY.insert(y);
        }
    }
};

// 最大マッチング
int max_matching_size(BipartiteGraph &g) { // return -> 最大マッチングサイズ.
    return max_flow(g, g.G.size()-2, g.G.size()-1);
}

// 最大マッチングを構築. (matchingに格納して返す)
set<pair<int, int>> max_matching(BipartiteGraph &g) {
    // g : 二部グラフ
    // matching : 最大マッチング集合.(構築対象)
    set<pair<int, int>> matching;
    int sz = max_flow(g, g.G.size()-2, g.G.size()-1);
    for (int i : g.setX) {
        for (auto &&e: g.G[i]) {
            // マッチング辺の条件.
            if ( e.cap == 0 )
                matching.emplace(i, e.to);
        }
    }
    return matching;
}


int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    vector<int> X(M);
    vector<int> Y(M);
    UnionFind uf(M);

    REP(i,M) {
        cin >> X[i] >> Y[i];
        X[i]--;
        Y[i]--;
    }

    BipartiteGraph g(N*N);
    
    REP(i,M) {
        g.add_edge(X[i], N+Y[i]);
        FOR(j, i+1, M) {
            if (X[i] == X[j] || Y[i] == Y[j]) {
                uf.unite(i, j);
            }
        }
    }

    // Maximum
    int max = M;
    REP(i, M) {
        if (uf.par[i] == i) {
            max--;
        }
    }

    // Minimum
    int min = M - max_matching_size(g);
    
    cout << min << " " << max << endl;
}




Measured memory_bytes: 34248