#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
void merge(pii &x, int y) {
    if (x.first > y) x.second = x.first, x.first = y;
    else if (x.second > y) x.second = y;
}
int query(const pii &x, int y) {
    return y == x.first ? x.second : x.first;
}
#define rep(i, a, b) for (int i = a, I = b; i <= I; ++i)
#define per(i, a, b) for (int i = a, I = b; i >= I; --i)
template<typename T> void down(T &x, T y) { if (x > y) x = y; }

const int N = 2000005;
int n, m, x[N], y[N], z[N], par[N];
int dep[N], cnt[N], siz[N], fa[N], cnt1[N], anc[N], sum[N];
pii mn[N];
bool has_edge[N], has_3[N], sz[N], sum1[N], flag[N], tag[N];
vector<int> e[N], e1[N];
vector<pair<int, int>> edges;

int find(int x) {
    while (x != par[x]) x = par[x] = par[par[x]];
    return x;
}
void merge(int x, int y) {
    int u = find(x), v = find(y);
    if (u == v) {
        sz[u] ^= 1;
    } else {
        sz[u] ^= sz[v] ^ 1;
        par[v] = u;
    }
}

void dfs(int u) {
    mn[u] = pii(1e9, 1e9);
    for (auto i : e[u]) {
        int v = z[i] ^ u;
        if (v == fa[u]) continue;
        if (!dep[v]) {
            ++siz[u];
            dep[v] = dep[u] + 1;
            fa[v] = u;
            int tmp = cnt[u];
            dfs(v);
            has_edge[v] = (cnt[u] > tmp);
            siz[u] += siz[v];
            sum[u] += sum[v];
            merge(mn[u], mn[v].first);
        } else if (dep[v] < dep[u]) {
            ++cnt[v];
            ++siz[v];
            merge(mn[u], dep[v]);
            sum[fa[u]] += 1, sum[v] -= 1;
            sum1[u] ^= 1;
            ++cnt1[u], ++cnt1[v];
            if (dep[v] == dep[u] - 2) has_3[u] = 1;
            edges.push_back({u, v});
        }
    }
}

bool dfs1(int u) {
    for (auto i : e[u]) {
        int v = z[i] ^ u;
        if (fa[v] != u) continue;
        if (dfs1(v)) return 1;
    }
    if (has_3[u]) {
        int v = fa[u], w = fa[v];
        bool has_uv = has_edge[u];
        bool has_uw = (query(mn[u], dep[w]) <= dep[w]);
        bool has_vw = (query(mn[v], mn[u].first) <= dep[w]);
        int cnt = has_uv + has_uw + has_vw;
        if (cnt >= 2) return 1;
        bool sz_u = siz[u] % 2;
        bool sz_v = (siz[v] - siz[u] - 1) % 2;
        bool sz_w = (siz[v] + 1) % 2; // siz[root] - siz[v] - 2
        // sizes of each part (assuming it's disconnected)
        if (cnt == 0) return !sz_u && !sz_v && !sz_w;
        if (has_uv) return !sz_w;
        if (has_uw) return !sz_v;
        if (has_vw) return !sz_u;
    }
    for (auto v : e[u]) anc[dep[v]] = v;
    bool tmp = 0;
    for (auto v : e[u]) {
        if (fa[v] == u) continue;
        int d = dep[v];
        if (d < dep[u]) {
            int w = anc[d - 1];
            if (!w) continue;
            if (sum[v] > 1) {
                tmp = 1;
                break;
            }
            bool sz_v = (siz[v] - 1) & 1;
            if (!sz_v) {
                tmp = 1;
                break;
            }
        } else {
            int w = anc[d + 1];
            if (!w) continue;
            if (sum[v] > 1) {
                tmp = 1;
                break;
            }
            bool sz_w = siz[w] & 1;
            if (!sz_w) {
                tmp = 1;
                break;
            }
        }
    }
    for (auto v : e[u]) anc[dep[v]] = 0;
    return tmp;
}

bool dfs2(int u) {
    int mx = cnt1[u];
    bool sz = (siz[u] ^ sum[u] ^ sum1[u]) & 1; // all - siz[u] - 1 - sum1[u]
    for (auto i : e[u]) {
        int v = z[i] ^ u;
        if (fa[v] != u) continue;
        if (dfs2(v)) return 1;
        if (mn[v].first < dep[u]) {
            sz ^= (sum[v] ^ siz[v]) & 1;
            ++mx;
        } else {
            mx += (siz[v] % 2 == 0);
        }
    }
    if (!sz) ++mx;
    return mx >= 3;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);

    cin >> m >> n;
    rep(i, 1, m) {
        cin >> x[i] >> y[i];
        e[x[i]].push_back(i);
        e[y[i]].push_back(i);
        z[i] = x[i] ^ y[i];
    }

    rep(i, 1, n) par[i] = i;
    rep(i, 1, m) merge(x[i], y[i]);

    rep(i, 1, n) {
        if (find(i) != i || !sz[i]) continue;
        dep[i] = 1, dfs(i);
        flag[i] = dfs1(i);
    }

    for (auto it : edges) {
        int x = it.first, y = it.second;
        if (cnt1[x] < cnt1[y] || x < y) swap(x, y);
        e1[x].push_back(y);
    }
    rep(i, 1, n) {
        if (flag[find(i)]) continue;
        for (auto j : e1[i]) for (auto k : e1[j]) tag[k] = 1;
        bool cur = 0;
        for (auto j : e1[i]) cur |= tag[j];
        flag[find(i)] |= cur;
        for (auto j : e1[i]) for (auto k : e1[j]) tag[k] = 0;
    }

    int ans1 = 0, ans2 = 0;
    rep(i, 1, n) {
        if (find(i) != i || !sz[i] || flag[i]) continue;
        ++(dfs2(i) ? ans2 : ans1);
    }
    cout << ans1 << " " << ans2 << "\n";

    return 0;
}