#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

const int MAXN = 4'000'100;
vector<pair<int, int>> G[MAXN];
int tin[MAXN];
int tup[MAXN];
int ttime = 0;

vector<int> stack;
vector<vector<int>> edge_comps;
int edge_comp_id[MAXN];

vector<int> falling_off[MAXN];

int used[MAXN];
vector<int> vertices;

void dfs_dot(int v, int p) {
  vertices.emplace_back(v);
  tin[v] = ttime;
  tup[v] = ttime;
  ++ttime;
  used[v] = 1;
  for (auto [u, i] : G[v]) {
    if (i == p)
      continue;
    if (used[u] == 0) {
      int stack_sz = stack.size();
      stack.emplace_back(i);
      dfs_dot(u, i);
      if (tup[u] >= tin[v]) {
        // falls off
        edge_comps.emplace_back();
        while (stack.size() > stack_sz) {
          edge_comps.back().emplace_back(stack.back());
          stack.pop_back();
        }
        falling_off[v].emplace_back(edge_comps.size() - 1);
      }
      tup[v] = min(tup[v], tup[u]);
    } else if (used[u] == 1) {
      // edge up
      stack.emplace_back(i);
      tup[v] = min(tup[v], tin[u]);
    } else {
      // not interesting
    }
  }
  used[v] = 2;
}

vector<int> Gtree[MAXN];
int up[MAXN];
int tree_sz[MAXN];

void dfs_tree(int v, int p) {
  up[v] = p;
  for (int u : Gtree[v]) {
    if (u == p)
      continue;
    dfs_tree(u, v);
    tree_sz[v] += tree_sz[u];
  }
}

int id[MAXN];
vector<pair<int, int>> Gright[MAXN];

int cur_edges = 0;
int n;

int get_tree_sz(int from, int to) {
  if (up[to] == from)
    return tree_sz[to];
  return cur_edges - tree_sz[from];
}

bool check_even(int comp_id, int v) {
  return get_tree_sz(comp_id + n, v) % 2 == 0;
}

bool check_triangle(vector<int> vertices) {
  sort(vertices.begin(), vertices.end(), [](int a, int b) {
    return G[a].size() < G[b].size();
  });
  for (int i = 0; i < vertices.size(); ++i)
    id[vertices[i]] = i;
  for (int v : vertices) {
    for (auto [u, i] : G[v]) {
      if (id[u] > id[v]) {
        Gright[v].emplace_back(u, i);
      }
    }
  }
  vector<bool> state(vertices.size(), false);
  for (int v : vertices) {
    for (auto [u, i1] : Gright[v])
      state[id[u]] = true;
    for (auto [u, i1] : Gright[v]) {
      for (auto [x, i2] : Gright[u]) {
        if (state[id[x]]) {
          // triangle!
          // v, u, x
        //cerr << v << ' ' << u << ' ' << x << '\n';
          int comp_id = edge_comp_id[i1];
          bool ok = check_even(comp_id, v) && check_even(comp_id, u) && check_even(comp_id, x);
          //cerr << comp_id << '\n';

          //cerr << ok << '\n';
          if (ok)
            return true;
        }
      }
    }
    for (auto [u, i1] : Gright[v])
      state[id[u]] = false;
  }
  return false;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  
  int m;
  cin >> m >> n;
  vector<pair<int, int>> edges(m);
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    --a;
    --b;
    edges[i] = make_pair(a, b);
    G[a].emplace_back(b, i);
    G[b].emplace_back(a, i);
  }
  fill(used, used + n, 0);
  int ans_edge = 0;
  int ans_hedg = 0;
  vector<vector<int>> conn_comps;
  for (int i = 0; i < n; ++i) {
    if (used[i])
      continue;
    dfs_dot(i, -1);
    conn_comps.emplace_back(vertices);
    vertices.clear();
  }

  for (int i = 0; i < edge_comps.size(); ++i) {
    ////cerr << "edge_comp " << i << ": ";
    for (int j : edge_comps[i]) {
      ////cerr << j << ' ';
      edge_comp_id[j] = i;
    }
    ////cerr << '\n';
  }
  for (int i = 0; i < m; ++i) {
    auto [a, b] = edges[i];
    int j = n + edge_comp_id[i];
    Gtree[j].emplace_back(a);
    Gtree[j].emplace_back(b);
    Gtree[a].emplace_back(j);
    Gtree[b].emplace_back(j);
  }
  for (int i = 0; i < n + edge_comps.size(); ++i) {
    sort(Gtree[i].begin(), Gtree[i].end());
    Gtree[i].resize(unique(Gtree[i].begin(), Gtree[i].end()) - Gtree[i].begin());
  }

  for (int i = 0; i < edge_comps.size(); ++i)
    tree_sz[n + i] = edge_comps[i].size();

  vector<int> kek(edge_comps.size());

  for (int j = 0; j < conn_comps.size(); ++j) {
    auto& vertices = conn_comps[j];

    int root = vertices.front();
    dfs_tree(root, -1);

    cur_edges = 0;
    for (int v : vertices)
      cur_edges += G[v].size();
    cur_edges /= 2;
    if (cur_edges % 2 == 0)
      continue;

    // check triangle
    if (check_triangle(vertices)) {
      continue;
    }

    // check hedgehog
    bool can_hedge = false;
    for (int v : vertices) {
      int rem_deg = 0;
      if (falling_off[v].empty()) {
        if (G[v].size() >= 3)
          can_hedge = true;
        continue;
      }
      for (int u : Gtree[v]) {
        kek[u - n] = 0;
      }
      for (auto [u, i] : G[v]) {
        int j = edge_comp_id[i];
        ++kek[j];
      }
      for (int u : Gtree[v]) {
        int edges = get_tree_sz(v, u) - kek[u - n];
        rem_deg += kek[u - n] - edges % 2;
      }
      if (rem_deg >= 3)
        can_hedge = true;
    }
    if (can_hedge) {
      ++ans_hedg;
    } else {
      ++ans_edge;
    }
  }
  cout << ans_edge << ' ' << ans_hedg << '\n';

  return 0;
}