Problem: Problem Statement

"Rooks Game" is a single-player game and uses a chessboard which has $N \times N$ grid and $M$ rook pieces.

A rook moves through any number of unoccupied squares horizontally or vertically. When a rook can attack another rook, it can capture the rook and move to the square which was occupied. Note that, in Rooks Game, we don't distinguish between white and black, in other words, every rook can capture any of other rooks.

<image>

Initially, there are $M$ rooks on the board. In each move, a rook captures another rook. The player repeats captures until any rook cannot be captured. There are two types of goal of this game. One is to minimize the number of captured rooks, and the other is to maximize it.

In this problem, you are requested to calculate the minimum and maximum values of the number of captured rooks.

* * *

Input

The input consists of a single test case in the format below.

> $N$ $M$ $x_{1}$ $y_{1}$ $\vdots$ $x_{M}$ $y_{M}$

The first line contains two integers $N$ and $M$ which are the size of the chessboard and the number of rooks, respectively ($1 \le N, M \le 1000$). Each of the following $M$ lines gives the position of each rook. The $i$-th line with $x_{i}$ and $y_{i}$ means that the $i$-th rook is in the $x_{i}$-th column and $y_{i}$-th row ($1 \le x_{i}, y_{i} \le N$). You can assume any two rooks are not in the same place.

Output

Output the minimum and maximum values of the number of captured rooks separated by a single space.

Examples

Input| Output
---|---


8 3
1 1
1 8
8 8


|


1 2



8 4
1 1
1 8
8 8
8 1


|


2 3



5 5
1 1
2 2
3 3
4 4
5 5


|


0 0



100 1
100 100


|


0 0



10 12
1 2
1 4
1 6
3 6
5 6
10 7
8 7
6 7
4 7
2 7
7 3
9 5


|


7 8






Example

Input




Output

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

struct UnionFind{
  int num;//連結成分の数
  vector<int> r,p;//そのグループのサイズ,自分の親っぽいやつ
  UnionFind(){}
  UnionFind(int n):num(n),r(n,1),p(n,0){iota(p.begin(),p.end(),0);}

  int find(int x){//どのグループに所属するか
    return (x==p[x]?x:p[x]=find(p[x]));//xがグループの名前と一致するまでxを親にする
  }

  bool same(int x,int y){//同じグループかどうか
    return find(x)==find(y);
  }

  void unite(int x,int y){//xとyを同じグループにする
    x=find(x);y=find(y);//xとyのグループの名前をどっちかが変える
    if(x==y) return;
    if(r[x]<r[y]) swap(x,y);//サイズが大きい方をxとする
    r[x]+=r[y];//yの親をxにする（今までyだったグループ名がxになる）
    p[y]=x;
    num--;
  }

  int size(int x){//グループの大きさ
    return r[find(x)];
  }

  int count() const{//グループの数
    return num;
  }
};
template<typename T,bool directed>//directedは有向のこと
struct Fordfulkerson{
  struct edge{
    int to,cap,rev;
    edge(){}
    edge(int to,int cap,int rev):to(to),cap(cap),rev(rev){}
  };

  vector<vector<edge> > G;
  vector<int> used;

  Fordfulkerson(){}
  Fordfulkerson(int n):G(n),used(n){}//n個の頂点

  void add_edge(int from,int to,T cap){
    G[from].emplace_back(to,cap,G[to].size());//edgeのrevには逆辺の番号が入る
    G[to].emplace_back(from,directed?0:cap,G[from].size()-1);//有向グラフならcapは0
  }

  T dfs(int v,int t,T f){//v->tにfの流量を道が見つかり次第通していく感じ　通った量が返り値
    if(v==t) return f;//ゴール
    used[v]=true;//通った確認
    for(int i=0;i<(int)G[v].size();i++){
      edge &e = G[v][i];
      if(!used[e.to]&&e.cap>0){//まだ通ってなくてcap的にいける場所があるなら
        T d=dfs(e.to,t,min(f,e.cap));//そこからtまで通せるだけ通そうとして見る
        if(d>0){//dだけ通った
          e.cap-=d;//流量を減らす
          G[e.to][e.rev].cap+=d;//逆辺の流量を増やす
          return d;//d通せた
        }
      }
    }
    return 0;
  }

  int flow(int s,int t,T lim){
    T fl=0;
    while(1){
      fill(used.begin(),used.end(),0);//usedの初期化
      T f=dfs(s,t,lim);//sからtまで逆辺を考慮しつつ通す
      if(f==0) break;//全く通らないなら終了
      fl+=f;//通ってるなら流量を増やす
      lim-=f;//初期流量を減らす
    }
    return fl;
  }

  int flow(int s,int t){//全力で流す
    return flow(s,t,numeric_limits<T>::max()/2);
  }

};

signed main(){
  int N,M;cin>>N>>M;
  std::vector<int> x(M),y(M);
  for(int i=0;i<M;i++)cin>>x[i]>>y[i];
  int ans1,ans2;
  UnionFind uf(M);
  for(int i=0;i<M;i++)
    for(int j=i+1;j<M;j++)
      if(x[i]==x[j]||y[i]==y[j])uf.unite(i,j);
  ans2=M-uf.count();
  Fordfulkerson<int,1> fl(10000);
  set<int> usedx,usedy;
  for(int i=0;i<M;i++){
    fl.add_edge(x[i],y[i]+1000,1);
    if(!usedx.count(x[i])){
      fl.add_edge(0,x[i],1);
      usedx.insert(x[i]);
    }
    if(!usedy.count(y[i])){
      fl.add_edge(y[i]+1000,3000,1);
      usedy.insert(y[i]);
    }
  }
  ans1=M-fl.flow(0,3000);
  cout<<ans1<<" "<<ans2<<endl;
}