#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define ff ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N=1e5+7;

vector<int>vec[N];
int root;
vector<int>vec_root;
int vis[N] , depth[N];
int mp1[N] , mp2[N] , mp3[N];
int root_tp[N];
pair<int , int>pp[N];
void dfs(int tp , int p , int deep)
{
	vis[p]=1;
	depth[p]=deep;
	root_tp[p]=tp;
	int sz=vec[p].size();
	if(sz==1&&p!=root)
	{
		mp1[p]=1;
		mp2[p]=0;
		mp3[p]=0;
		return;
	}
	for(int i=0;i<sz;i++)
	{
		if(vis[vec[p][i]]==1) continue;
		dfs(tp , vec[p][i]  , deep+1);
		if(mp1[vec[p][i]]&1) mp2[p]++;
		else mp3[p]++;
		mp1[p]+=mp1[vec[p][i]]+1; 
	}
}
signed main()
{
	int n , m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u , v;
		cin>>u>>v;
		pp[i]={u , v};
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	int odd=0 , even=0;
	for(int i=1;i<=n;i++)
	{
		if(vis[i]==0)
		{
			root=i;
			vec_root.push_back(i);
			dfs(i , root , 0);
			if(mp1[i]==0) mp1[i]=1;
			if(mp1[i]&1) odd++;
			else even++;
		}
	}
	cout<<odd<<" "<<even<<endl;
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		int oddd=odd , evenn=even;
		if(mp1[root_tp[i]]&1) oddd--;
		else evenn--;
		if((mp1[root_tp[i]]-mp1[i])&1) oddd++;
		else if((mp1[root_tp[i]]-mp1[i])!=0) evenn++;
		oddd+=mp2[i];
		evenn+=mp3[i];
		if((oddd%2==0)&&(evenn%2==0)) ans++;
	}
//	for(int i=1;i<=n;i++) cout<<mp1[i]<<" "<<mp2[i]<<" "<<mp3[i]<<endl;
//	for(int i=1;i<=n;i++) cout<<depth[i]<<endl;
	for(int i=1;i<=m;i++)
	{
		int oddd=odd , evenn=even;
		if(mp1[root_tp[pp[i].first]]&1) oddd--;
		else evenn--;		
		if(depth[pp[i].first]>depth[pp[i].second])
		{
			if((mp1[root_tp[pp[i].first]]-mp1[pp[i].first])&1)oddd++;
			else evenn++;
			if(mp1[pp[i].first]&1) oddd++;
			else evenn++;
		}
		else
		{
			if((mp1[root_tp[pp[i].second]]-mp1[pp[i].second])&1)oddd++;
			else evenn++;
			if(mp1[pp[i].second]&1) oddd++;
			else evenn++;
		}
		if((oddd%2==0)&&(evenn%2==0)) ans++;
	}
	cout<<ans<<endl;
	return 0;
}