#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define vi vector <int>
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f))
#define uint unsigned int 
#define ull unsigned long long 
#define ld long double
#define i128 __int128 
using namespace std; 
const int N = 4e6 + 7, mod = 1e9 + 7;

namespace solver {
	mt19937_64 orz(114514);
	int n, h, su[N], sv[N], deg[N], vis[N], fae[N];
	int ehd[N], ev[N], enx[N], eid;
	void eadd(int u, int v) {
		++eid, enx[eid] = ehd[u], ev[eid] = v, ehd[u] = eid;
	}
	int use[N];
	int fa[N], dfn[N], low[N], idtot;
	ull F[N], val[N];
	vi e[N], vc[N];
	void dfs(int x) {
		dfn[x] = low[x] = ++idtot;
		for(int i = ehd[x]; i; i = enx[i]) 
			if(!dfn[ev[i]]) 
				fa[ev[i]] = x, fae[ev[i]] = i, use[i >> 1] = true, dfs(ev[i]);
			else if(dfn[ev[i]] < dfn[x] && !use[i >> 1]) {
				ull cur = F[i >> 1] = orz();
				val[x] ^= cur;
				val[ev[i]] ^= cur;
			} 
	} 
	
	int siz[N];
	void dfs2(int x) {	
		siz[x] = 0;
		for(int i = ehd[x]; i; i = enx[i]) 
			if(dfn[ev[i]] > dfn[x]) 
				siz[x] += 1;
		for(auto v : e[x]) {
			dfs2(v);
			siz[x] += siz[v];
			val[x] ^= val[v];
		}
	}

	
	void link(int u, int v) {
		++n;
		su[n] = u, sv[n] = v;
	}
	
	int hd[N], to[N], nx[N];
	
	inline int SZ(int x, int y, int z) {
		int all = n;
		if(fa[x] == y || fa[x] == z) {
			all = siz[x];
		}
		if(fa[y] == x) {
			all -= siz[y] + 1;
			if(fa[x] != z) --all;
		}
		if(fa[z] == x) {
			all -= siz[z] + 1;
			if(fa[x] != y) --all;
		}
		return all;
	}
	
	pair < int, int > work() {
		eid = 1;
//		cout << "deg seq = ";
//		L(i, 1, h) {
//			cout << deg[i] << ' ';
//		}
//		cout << endl;
		if(n == 1) {
			return make_pair(1, 0);
		}
		L(i, 1, n) {
			++deg[su[i]];
			++deg[sv[i]];
		}
		
		int ok = n == h;
		L(i, 1, h) 
			ok &= deg[i] == deg[1];
//		cout << h << " : deg seq = "; 
//		L(i, 1, h) 
//			cout << deg[i] << ' ';
//		cout << endl;
		if(ok && n != 3) {
			return make_pair(1, 0);
		}
		
		L(i, 1, n) {
			int u = su[i], v = sv[i];
			if(deg[u] > deg[v]) swap(u, v);
			else if(deg[u] == deg[v] && u > v) swap(u, v);
			to[i] = v;
			nx[i] = hd[u];
			hd[u] = i;
		}
		
		L(i, 1, n) {
			eadd(su[i], sv[i]);
			eadd(sv[i], su[i]);
		}
		dfs(1);
		L(i, 2, h) e[fa[i]].emplace_back(i); 
		dfs2(1);
		L(i, 2, h) F[fae[i] >> 1] = val[i];
		
		L(i, 1, h) {
			for(int id = hd[i]; id; id = nx[id]) 
				vis[to[id]] = id;
			for(int id = hd[i]; id; id = nx[id]) {
				int j = to[id];
				for(int di = hd[j]; di; di = nx[di]) {
					int k = to[di];
					if(!vis[k]) continue;
					ull ij = F[id];
					ull jk = F[di];
					ull ik = F[vis[k]];
					
//					cout << i << ' ' << j << ' ' << k << endl;
					
					int ok = 1;
					if(ij == ik) {
						if(SZ(i, j, k) & 1)
							ok = 0;
					}
					if(ij == jk) {
						if(SZ(j, k, i) & 1)
							ok = 0;
					}
					if(ik == jk) {
						if(SZ(k, i, j) & 1)
							ok = 0;
					}
					if(ok) 
						return make_pair(0, 0);
				}
			}
			for(int id = hd[i]; id; id = nx[id]) 
				vis[to[id]] = 0;
		} 
		return make_pair(0, 1);
	}
	void clear() {
		L(i, 1, max(n, h)) 
			su[i] = sv[i] = 0, deg[i] = 0, 
			e[i].clear(), dfn[i] = 0, low[i] = 0, fa[i] = 0, hd[i] = 0, vis[i] = 0, 
			ehd[i] = 0, use[i] = 0, F[i] = 0, val[i] = 0, fa[i] = 0, vc[i].clear(); 
		n = h = 0, eid = 1, idtot = 0;
	}
}

int n, h, f[N];
vi son[N];

int ehd[N], ev[N], enx[N], eid = 1;
void eadd(int u, int v) {
	++eid, ev[eid] = v, enx[eid] = ehd[u], ehd[u] = eid;
} 

inline int find(int x) {
	return f[x] == x ? x : f[x] = find(f[x]);
}
int su[N], sv[N];

vi G[N];

queue < int > q;
int deg[N], del[N], usee[N];
void ban(int u) {
	del[u] = true;
	for(int i = ehd[u]; i; i = enx[i]) if(!del[ev[i]]) {
		--deg[ev[i]];
		if(deg[ev[i]] <= 2) q.push(ev[i]);
	}
}

void gank(int u, int v, int id) {
	if(deg[u] == 2) swap(u, v);
	for(int j = ehd[v]; j; j = enx[j]) {
		if(!del[ev[j]] && ev[j] != u) {
			usee[id >> 1] = usee[j >> 1] = true;
			ban(u), ban(v);
		}
	}
}

int id[N];
void Main() {
	cin >> n >> h, eid = 1;
	L(i, 1, max(n, h)) 
		G[i].clear(), son[i].clear(), 
		ehd[i] = 0, deg[i] = 0, del[i] = 0, usee[i] = 0;
	
	L(i, 1, h) 
		f[i] = i;
	set < pair < int, int > > st;
	L(i, 1, n) {
		int u, v;
		cin >> u >> v;
		if(u > v) swap(u, v);
		st.insert(make_pair(u, v));
		assert(u != v);
		assert(1 <= u && u <= h);
		assert(1 <= v && v <= h);
		eadd(u, v);
		eadd(v, u);
		su[i] = u, sv[i] = v;
		deg[u] += 1;
		deg[v] += 1;
	}
	
	L(i, 1, h) {
		if(deg[i] <= 2) {
			q.push(i);
		}
	}
	
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		if(del[u]) continue;
		for(int i = ehd[u]; i; i = enx[i]) {
			int v = ev[i];
			if(!del[u] && !del[v]) {
				if((deg[u] == 1 && deg[v] == 2) || (deg[v] == 1 && deg[u] == 2)) {
					gank(u, v, i);
					break;
				}
			}
		}
	}
	
	L(i, 1, n) if(!usee[i]) {
		f[find(su[i])] = find(sv[i]);
	}
	L(i, 1, n) if(!usee[i]) {
		G[find(su[i])].emplace_back(i);
	}
	L(i, 1, h) {
		son[find(i)].emplace_back(i);
	}
	
	int cnt1 = 0, cnt2 = 0;
	L(i, 1, h) if(find(i) == i) {
		if(sz(G[i]) % 2 == 0) {
			continue;
		}
		solver :: n = 0;
		solver :: h = sz(son[i]);
		L(j, 0, sz(son[i]) - 1) 
			id[son[i][j]] = j + 1;
		for(auto &t : G[i]) {
			int u = id[su[t]];
			int v = id[sv[t]];
			solver :: link(u, v); 
		}
		auto pr = solver :: work();
		cnt1 += pr.first;
		cnt2 += pr.second;
		solver :: clear();
	}
	cout << cnt1 << ' ' << cnt2 << '\n';
//	cout << n << " and " << h << endl;
}

int main() {
 	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	Main();
//	int t; cin >> t; while(t--) Main();
	return 0;
}

/*
1
9 9
2 5
2 9
3 6
1 4
2 3
6 8
7 9
5 8
4 9
*/