#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
void operator+=(pii &x, const pii &y) { x.first += y.first, x.second += y.second; }
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];
pii mn[N];
bool has_edge[N], has_3[N], sz[N], sum[N], sum1[N];
vector<int> e[N];

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);
    int mn1 = 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];
            down(mn1, dep[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;
        }
    }
}

bool dfs1(int u) {
    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 i : e[u]) {
        int v = z[i] ^ u;
        if (fa[v] != u) continue;
        if (dfs1(v)) return 1;
    }
    return 0;
}

bool dfs2(int u) {
    int mx = cnt1[u];
    bool sz = (siz[u] & 1) ^ sum[u] ^ sum1[u]; // 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] % 2);
            ++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]);

    pii ans(0, 0);
    rep(i, 1, n) {
        if (find(i) != i || !sz[i]) continue;
        dep[i] = 1, dfs(i);
        if (dfs1(i)) continue;
        ans += (dfs2(i) ? pii(0, 1) : pii(1, 0));
    }

    cout << ans.first << " " << ans.second << "\n";    

    return 0;
}