#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=4e6+5,M=N*20+5,K=600+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const ll INF=1e18+7;mt19937 rnd(263082);
int m,n,X[N],Y[N],In[N];vector<int> S[N],G[N];
int dep[N];
int dp[N],flag;
vector<int> pot;
int sum;
void dfs1(int x,int La){
	pot.emplace_back(x);sum++;
	dp[x]=(La>0);dep[x]=dep[La]+1;
	for(int i:S[x]) if(!dep[i]){
		dfs1(i,x);dp[x]+=dp[i];sum--;
	}else if(dep[x]<dep[i]) dp[x]++,sum--;
	int Ct=dp[x];
	for(int i:S[x]) if(i^La&&dep[i]<dep[x]) Ct++;
	if(Ct>=3) flag=1;dp[x]&=1;
}
int dfn[N],low[N],dh,st[N],sh,Ct,fa[N],Si[N];vector<int> P[N];
void con(int x,int y){P[x].emplace_back(y);P[y].emplace_back(x);}
void dfs2(int x,int La){
	dfn[x]=low[x]=++dh;st[++sh]=x;
	for(int i:S[x]) if(i^La){
		if(dfn[i]) {low[x]=min(low[x],dfn[i]);continue;}dfs2(i,x);low[x]=min(low[x],low[i]);
		if(low[i]>=dfn[x]){con(++Ct,x);/*cerr<<"Pt "<<Ct<<'\n'<<x<<' ';*/while(st[sh+1]^i) /*cerr<<st[sh]<<' ',*/con(Ct,st[sh--]);/*cerr<<'\n';*/}
	}
}
void dfs3(int x,int La){fa[x]=La;for(int i:P[x]) if(i^La) dfs3(i,x);}
void dfs4(int x,int La){for(int i:P[x]) if(i^La) dfs4(i,x),Si[x]+=Si[i];}
int g[N],gs[N];
int check(int x,int y,int z){
	cerr<<x<<' '<<y<<' '<<z<<'\n';
	int cir=fa[x];if(fa[y]==fa[z]) cir=fa[y];
	cerr<<cir<<'\n';
	auto find=[&cir](int x){
		if(fa[x]==cir){
			if(g[x]==2&&Si[x]&1) return 0;
		} else{
			if(g[cir]==2&&!(Si[cir]&1)) return 0;
		}
		return 1;
	};
	cerr<<find(z)<<'\n';
	return find(x)&&find(y)&&find(z);
}
int calc(){
	for(int i:pot){
		for(int j:G[i]) gs[j]++;
		for(int j:G[i]) for(int h:G[j]) if(gs[h]&&check(i,j,h)) return 1;
		for(int j:G[i]) gs[j]=0;
	}
	return 0;
}
void Solve(){
	int i,j;scanf("%d%d",&m,&n);
	for(i=1;i<=m;i++) scanf("%d%d",&X[i],&Y[i]),In[X[i]]++,In[Y[i]]++;
	for(i=1;i<=m;i++) S[X[i]].emplace_back(Y[i]),S[Y[i]].emplace_back(X[i]);
	for(i=1;i<=m;i++){
		if(In[X[i]]>In[Y[i]]) swap(X[i],Y[i]);
		G[X[i]].emplace_back(Y[i]);
	} 
	int ans1=0,ans2=0;Ct=n;
	for(i=1;i<=n;i++) if(!dep[i]){
		pot.clear();flag=sum=0;dfs1(i,0);if(!dp[i]) continue;
		int LC=Ct;sh=0;dfs2(i,0);dfs3(i,0);
		for(int j:pot) for(int h:S[j]) {
			if(fa[h]==fa[j]||fa[fa[j]]==h) g[j]++,dfn[j]<dfn[h]&&(Si[fa[j]]++);else g[fa[h]]++,dfn[j]<dfn[h]&&(Si[fa[h]]++);
		}
		dfs4(i,0);//if(i%1000==0) cerr<<pot.size()<<' '<<Ct<<' '<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
		if(calc()) continue;
		for(j=LC+1;j<=Ct;j++) if(Si[j]>P[j].size()) flag=1;
		if(!flag) ans1++;
		else ans2++;
	}
	printf("%d %d\n",ans1,ans2);
}
int main(){
	int t=1;
	// scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}