#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define per(i, a, b) for (int i = a; i >= b; i--)
using namespace std;

typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef long long ll;

template <typename _T>
inline void read(_T &f) {
    f = 0; _T fu = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') { fu = -1; } c = getchar(); }
    while (c >= '0' && c <= '9') { f = (f << 3) + (f << 1) + (c & 15); c = getchar(); }
    f *= fu;
}

template <typename T>
void print(T x) {
    if (x < 0) putchar('-'), x = -x;
    if (x < 10) putchar(x + 48);
    else print(x / 10), putchar(x % 10 + 48);
}

template <typename T>
void print(T x, char t) {
    print(x); putchar(t);
}

const int N = 4e6 + 5;

vector <int> adj[N], tr[N], edg[N];
int fa[N], vis[N], s[N], seq[N], dep[N], ou[N], ov[N], deg[N], viscyc[N];
int n, m, len, ans1, ans2, olen;

void dfs1(int u) {
    vis[u] = 1; seq[++len] = u;
    for (auto v : adj[u]) {
        if (!vis[v]) {
            fa[v] = u; dep[v] = dep[u] + 1;
            dfs1(v);
        }
    }
}

int par[N][21];
int up[N], tofa[N], siz[N];
void dfs2(int u) {
    par[u][0] = fa[u];
    for (int i = 1; i <= 20; i++) par[u][i] = par[par[u][i - 1]][i - 1];
    for (auto v : tr[u]) {
        dfs2(v);
        s[u] += s[v]; siz[u] += siz[v];
    }
    assert(s[u] >= 0);
}

int jump(int u, int k) {
    assert(k >= 0);
    for (int i = 0; i <= 20; i++) {
        if ((k >> i) & 1) {
            u = par[u][i];
        }
    }
    assert(u);
    return u;
}

int main() {
    read(m); read(n);
    // assert(m >= 2 && n >= 3 && n <= 2 * m && n <= 1000000 && m <= 2000000);
    for (int i = 1; i <= m; i++) {
        int u, v;
        read(u); read(v);
        adj[u].push_back(v);
        adj[v].push_back(u);
        assert(u != v);
        assert(1 <= u && u <= n && 1 <= v && v <= n); 
    }
    for (int _ = 1; _ <= n; _++) {
        if (vis[_]) continue;
        len = 0; dfs1(_); olen = 0;
        for (int i = 1; i <= len; i++) {
            int u = seq[i];
            for (auto v : adj[u]) {
                if (dep[u] > dep[v]) continue;
                ++siz[v];
                if (fa[v] == u) {
                    tr[u].push_back(v);
                    // fprintf(stderr, "u = %d, v = %d\n", u, v);
                    continue;
                }
                ++olen; ou[olen] = u; ov[olen] = v;
                ++s[v]; --s[u];
            }
        }
        int all = olen + len - 1;
        if (all % 2 == 0) continue;
        dfs2(_);
        for (int i = 1; i <= olen; i++) {
            ++up[ov[i]];
            ++tofa[jump(ov[i], dep[ov[i]] - dep[ou[i]] - 1)];
        }

        // check size = 3 cycle
        int can = 0;
        for (int i = 1; i <= olen; i++) {
            ++deg[ou[i]]; ++deg[ov[i]];
        }
        for (int i = 1; i <= olen; i++) {
            if (deg[ou[i]] < deg[ov[i]] || (deg[ou[i]] == deg[ov[i]] && ou[i] < ov[i])) {
                edg[ov[i]].push_back(ou[i]);
            } else {
                edg[ou[i]].push_back(ov[i]);
            }
        }
        for (int i = 1; i <= len; i++) {
            int u = seq[i];
            for (auto v : edg[u]) viscyc[v] = 1;
            for (auto v : edg[u]) for (auto vv : edg[v]) {
                can |= viscyc[vv];
            }
            for (auto v : edg[u]) viscyc[v] = 0;
            if (can) break;
        }
        if (can) continue;
        for (int i = 1; i <= olen; i++) {
            if (deg[ou[i]] < deg[ov[i]] || (deg[ou[i]] == deg[ov[i]] && ou[i] < ov[i])) {
                edg[ou[i]].push_back(ov[i]);
            } else {
                edg[ov[i]].push_back(ou[i]);
            }
        }
        for (int i = 1; i <= len; i++) {
            int u = seq[i];
            for (auto v : edg[u]) viscyc[v] = 1;
            for (auto v : edg[u]) {
                // fprintf(stderr, "v = %d, fa[v] = %d\n", v, fa[v]);
                // fprintf(stderr, "u = %d, v = %d\n", u, v);
                if (viscyc[fa[v]]) {
                    if (s[v] > 1) can = 1;
                    else {
                        // fprintf(stderr, "u = %d, v = %d, fa[v] = %d, dep[u] = %d,  dep[v] = %d\n", u, v, fa[v], dep[u], dep[v]);
                        if (dep[u] > dep[v]) {
                            assert(siz[v] >= 3);
                            if ((siz[v] - 3) % 2 == 0) can = 1;
                        } else {
                            assert(siz[v] >= 2);
                            if ((siz[v] - 2) % 2 == 0) can = 1;
                        }
                    }
                }
            }
            for (auto v : edg[u]) viscyc[v] = 0;
            if (can) break;
        }
        if (can) continue;
        for (int i = 1; i <= olen; i++) {
            int u = ou[i], v = ov[i];
            // fprintf(stderr, "u = %d, v = %d\n", u, v);
            if (fa[fa[v]] == u) {
                int bel[3] = {0, 1, 2}, big[3] = {0, 0, 0}, cnt = 0;
                if (s[fa[v]] - (s[v] - tofa[v])) bel[1] = 0, ++cnt;
                assert(s[fa[v]] - (s[v] - tofa[v]) >= 0);
                if (s[v] - tofa[v] - 1) bel[2] = 0, ++cnt;
                assert(s[v] - tofa[v] - 1 >= 0);
                if (tofa[v]) bel[2] = 1, ++cnt;
                assert(tofa[v] >= 0);
                if (cnt >= 2) can = 1;
                else {
                    assert(all - siz[fa[v]] >= 0);
                    big[bel[0]] += all - siz[fa[v]];
                    assert(siz[fa[v]] - siz[v] - 1 >= 0);
                    big[bel[1]] += siz[fa[v]] - siz[v] - 1;
                    assert(siz[v] - 2 >= 0);
                    big[bel[2]] += siz[v] - 2;
                    if (big[0] % 2 == 0 && big[1] % 2 == 0 && big[2] % 2 == 0) can = 1;
                }
            }
            if (can) break;
        }
        // fprintf(stderr, "_ = %d, len = %d, olen = %d\n", _, len, olen);
        if (can) continue;
        for (int i = 1; i <= len; i++) {
            int u = seq[i];
            if (s[u] > 1) {
                can = 1;
                break;
            }
            if ((int)edg[u].size() > 1) {
                can = 1;
                break;
            }
        }
        if (can) {
            ++ans2;
            continue;
        }
        for (int i = 1; i <= len; i++) {
            int u = seq[i], good = 0, good2 = 0;
            for (auto v : tr[u]) {
                if (!s[v] && (siz[v] - 1) % 2 == 0) ++good;
                good2 += s[v];
            }
            if (fa[u]) good2 += s[u];
            if (fa[u] && !s[u] && (all - siz[u]) % 2 == 0) ++good;
            if (good >= 3 || good2 >= 3 || (good2 && good)) {
                can = 1;
                break;
            }
        }
        if (can) {
            ++ans2;
            continue;
        }
        ++ans1;
    }
    print(ans1, ' '); print(ans2, '\n');
    return 0;
}