#include <bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
using pi = pair <int, int> ; 
using ll = long long ; 
void cmn(int & x, int y) {
    if(x > y) x = y; 
}
void cmx(int &x , int y) {
    if(x < y) x = y; 
}
cs int oo = 1e9 + 7; 
cs int N = 2e6 + 5; 
int n, m;
vector <int> e[N], ee[N];
int vis[N];
int cnt; 
int d[N];
int fa[N];
void dfs(int u, int fa, vector <int> & S, vector <pi> & E) {
    vis[u] = ++ vis[0]; 
    S.pb(u);
    d[u] = d[:: fa[u] = fa] + 1; 
    for(int v : e[u]) 
    if(v != fa) {
        if(!vis[v]) ee[u].pb(v), ++ cnt, dfs(v, u, S, E);
        else if(vis[v] < vis[u]) E.pb({u, v}), ++ cnt; 
    }
}
vector <int> p[N];
int id[N];
int w[N], mn[N];
vector <int> suf[N], pre[N];
int sz[N];
bool FLAG; 
int hav[N]; // hav[u] means that there is an edge from subtree u to fa[u]
bool check1(int u, int v) {
    assert(fa[u] == v) ;
    if(mn[u] <= d[v]) return 1; 
    return 0; 
}
bool check2(int u, int v, int z) {
    assert(fa[u] == v);
    assert(fa[v] == z);
    
    int idu = id[u];
    int mnv = min(id[u] ? pre[v][id[u] - 1] : oo, id[u] + 1 < suf[v].size() ? suf[v][id[u] + 1] : oo);
    if(mn[u] <= d[z] && mnv <= d[z]) return 1; 
    if(mn[u] == d[v] && mnv <= d[z]) return 1; 
    if(mn[u] > d[v] && mnv <= d[z]) {
        return sz[u] % 2 == 0;  
    }
    if(mnv > d[z]) {
        if(hav[u] && mn[u] <= d[z]) return 1; 
        if(mn[u] == d[v]) return sz[v] % 2 == 0;
        if(mn[u] <= d[z]) {
            return (sz[u] - sz[v]) % 2 == 0; 
        }
        if(mn[u] > d[v]) {
            return sz[u] % 2 == 0 && (sz[v] - sz[u]) % 2 == 0; 
        }
    }
    return 0; 

}
void dfs2(int u) {
    if(p[u].size()) {
        int fi = p[u][0];
        if(d[u] - d[fi] == 2) {
            if(check2(u, fa[u], fa[fa[u]])) {
                FLAG = 1; 
                return;
            }
        }
        for(int i = 0; i + 1 < p[u].size(); i++) {
            if(d[p[u][i]] - 1 == d[p[u][i + 1]]) {
                if(check1(p[u][i], p[u][i + 1])) {
                    FLAG = 1; 
                    return;
                }
            }
        }
    }
    for(int v : ee[u]) {
        dfs2(v);
        if(FLAG) return;
    }
}
vector <int> stk; 
void pre_dfs(int u) {
    for(int v : p[u]) ++ sz[u];
    stk.pb(u);
    for(int v : ee[u]) 
        pre_dfs(v), sz[u] += sz[v];

    for(int v : p[u]) {
        int w = stk[d[v]];
        hav[w] = 1; 
    }
    stk.pop_back();
    int n = ee[u].size();
    mn[u] = w[u] = 1e9; 
    for(int v : p[u]) cmn(w[u], d[v]);
    mn[u] = w[u];
    pre[u].resize(n); 
    suf[u].resize(n);
    for(int i = 0; i < n; i++)
        id[ee[u][i]] = i; 
    for(int i = 0; i < n; i++){
        if(i == 0) {
            pre[u][i] = mn[ee[u][i]];
        }
        else {
            pre[u][i] = min(pre[u][i - 1], mn[ee[u][i]]);
        }
    }
    for(int i = n - 1; ~i; i--) {
        if(i == n - 1) {
            suf[u][i] = mn[ee[u][i]];
        }
        else {
            suf[u][i] = min(suf[u][i + 1], mn[ee[u][i]]);
        }
    }
    cmn(mn[u], suf[u][0]);
}

cs int B = 128; 
bitset <B> eee[B];

unordered_map <ll, bool> mp; 
using u64 = unsigned long long;
struct BITSET {
    std::vector<u64> A;
};

bool hav_cir(vector <int> & S, vector <pi> & E) {
    int n = S.size();
    vector <int> d(n);
    static int id[N];
    for(int i = 0; i < n ;i++)
        id[S[i]] = i; 
    vector <vector <int> > e(n);
    for(auto & [u, v] : E) 
        u = id[u], v = id[v];
    for(auto [u, v] : E)
        e[u].pb(v), e[v].pb(u), mp[1ll * u * n + v] = mp[1ll * v * n + u] = 1; 
    vector <int> big; 
    for(int i = 0; i < n; i++) {
        if(e[i].size() < B) {
            for(int v : e[i]) { 
                for(int w : e[i]) {
                    if(mp[1ll * v * n + w]) {
                        return true; 
                    }
                }
            } 
        }
        else {
            big.pb(i);
        }
    }
}
void dfs3(int u) {
    for(int v : ee[u]) dfs3(v);
    int c = p[u].size();
    for(int v : ee[u]) {
        if(mn[v] >= d[u] || sz[v] % 2 == 0) ++ c; 
    }
    if(c + (sz[u] % 2 == 0) >= 3) {
        FLAG = 1; 
        return;
    }

    c = p[u].size() + 1;
    bool ooo = 1; 
    for(int v : ee[u]) {
        if(mn[v] > d[u] && hav[v]) {
            ooo = 1; 
            ++ c; 
        }
        if(mn[v] >= d[u] || sz[v] % 2 == 0) ++ c; 
    }
    if(ooo && c >= 3) {
        FLAG = 1; 
        return; 
    }
}
void work(vector <int> & S, vector <pi> & E, pi & ans) {
    if(hav_cir(S, E)) {
        return;
    }
    for(auto [u, v] : E) 
        p[u].pb(v);
    for(int x : S) {
        sort(p[x].begin(), p[x].end(), 
        [] (cs int & x, cs int & y) {
            return d[x] > d[y];
        });
    }
    pre_dfs(S[0]);
    FLAG = 0; 
    dfs2(S[0]);
    if(FLAG) {
        return; 
    }

    FLAG = 0; 
    static int cc[N];
    for(auto [u, v] : E) {
        ++ cc[u];
        ++ cc[v];
    }
    for(int x : S) 
    if(cc[x] >= 3) {
        ans.second += 1; 
        return; 
    }
    for(auto [u, v] : E) 
        p[v].pb(u);
    dfs3(S[0]);
    if(FLAG) {
        ans.second += 1; 
        return;
    }
    ans.first += 1;
    ans.second += 1; 
}

void Main() {
    cin >> m >> n; 
    for(int i = 1, u, v; i <= m; i++) {
        scanf("%d%d", &u, &v);
        e[u].pb(v), e[v].pb(u);
    }
    pi ans(0, 0);
    for(int i = 1;i <= n; i++) 
    if(!vis[i]) {
        cnt = 0;
        vector <int> S; 
        vector <pi> E;
        dfs(i, 0, S, E);
        if(cnt & 1) {
            work(S, E, ans);
        }
    }
    cout << ans.first << ' ' << ans.second << '\n';
}

int main() {
    #ifdef zqj
    freopen("1.in","r",stdin);
    #endif
    Main();
    return 0; 
}