#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];

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();
        }
      }
      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
          int comp_id = edge_comp_id[i1];
          bool ok = check_even(comp_id, v) && check_even(comp_id, u) && check_even(comp_id, x);
          
          if (ok)
            return true;
        }
      }
    }
    for (auto [u, i1] : Gright[v])
      state[id[u]] = false;
  }
  return false;
}

pair<int, int> solve(int N, vector<pair<int, int>> edges) {
  ttime = 0;
  n = N;
  int m = edges.size();
  for (int i = 0; i < m; ++i) {
    auto [a, b] = edges[i];
    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 < n + edge_comps.size(); ++i)
    tree_sz[i] = 0;

  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;
      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;
    }
  }

  for (int i = 0; i < n + edge_comps.size(); ++i)
    Gtree[i].clear();
  for (int i = 0; i < n; ++i) {
    Gright[i].clear();
    G[i].clear();
  }
  edge_comps.clear();


  return make_pair(ans_edge, ans_hedg);
}

bool all_comps_even(int n, vector<pair<int, int>> edges) {
  vector<vector<int>> G(n);
  for (auto [a, b] : edges) {
    G[a].emplace_back(b);
    G[b].emplace_back(a);
  }
  vector<bool> used(n, false);
  for (int i = 0; i < n; ++i) {
    if (used[i])
      continue;
    vector<int> cur;
    int q_sz = 0;
    used[i] = true;
    cur.emplace_back(i);
    while (q_sz < cur.size()) {
      int v = cur[q_sz];
      ++q_sz;
      for (int u : G[v]) {
        if (!used[u]) {
          used[u] = true;
          cur.emplace_back(u);
        }
      }
    }
    int total = 0;
    for (int v : cur) {
      //cerr << v << '(' << G[v].size() << ')' << ' ';
      total += G[v].size();
    }
    //cerr << '\n';
    total /= 2;
    //cerr << total << '\n';
    if (total % 2 == 1)
      return false;
  }
  return true;
}

pair<int, int> solve_dumb(int n, vector<pair<int, int>> edges) {
  int m = edges.size();
  vector<vector<int>> G(n);
  vector<vector<bool>> matrix(n, vector<bool>(n, false));
  for (auto [a, b] : edges) {
    G[a].emplace_back(b);
    G[b].emplace_back(a);
    matrix[a][b] = true;
    matrix[b][a] = true;
  }

  auto rem_edge = [](vector<pair<int, int>> edges, pair<int, int> edge) {
    int i = 0;
    pair<int, int> edge_rev(edge.second, edge.first);
    while (edges[i] != edge && edges[i] != edge_rev)
      ++i;
    edges.erase(edges.begin() + i);
    return edges;
  };

  int ans_edge = 0;
  int ans_hedg = 0;
  vector<bool> used(n, false);
  for (int i = 0; i < n; ++i) {
    if (used[i])
      continue;
    vector<int> cur;
    int q_sz = 0;
    cur.emplace_back(i);
    used[i] = true;
    while (q_sz < cur.size()) {
      int v = cur[q_sz];
      ++q_sz;
      for (int u : G[v]) {
        if (!used[u]) {
          used[u] = true;
          cur.emplace_back(u);
        }
      }
    }
    vector<pair<int, int>> cur_edges;
    for (int v : cur) {
      for (int u : G[v]) {
        if (v < u)
          cur_edges.emplace_back(v, u);
      }
    }
    if (cur_edges.size() % 2 == 0)
      continue;
    // 1) check triangle
    bool have = false;
    for (int v : cur) {
      for (int u : G[v]) {
        for (int x : G[u]) {
          if (x == v)
            continue;
          if (!matrix[v][x])
            continue;
          //cerr << v << ' ' << u << ' ' << x << '\n';
          auto kek = rem_edge(rem_edge(rem_edge(cur_edges, make_pair(u, v)), make_pair(v, x)), make_pair(u, x));
          if (all_comps_even(n, kek))
            have = true;
        }
      }
    }
    if (have)
      continue;
    // 2) check hedge
    for (int v : cur) {
      for (int i = 0; i < G[v].size(); ++i) {
        for (int j = i + 1; j < G[v].size(); ++j) {
          for (int k = j + 1; k < G[v].size(); ++k) {
            int a = G[v][i];
            int b = G[v][j];
            int c = G[v][k];
            auto kek = rem_edge(rem_edge(rem_edge(cur_edges, make_pair(v, a)), make_pair(v, b)), make_pair(v, c));
            if (all_comps_even(n, kek))
              have = true;
          }
        }
      }
    }
    if (have) {
      ++ans_hedg;
    } else {
      ++ans_edge;
    }
  }
  return make_pair(ans_edge, ans_hedg);
}

//#define STRESS

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

#ifdef STRESS
  for (int _ = 0; _ < 100100; ++_) {
    int n = rand() % 5 + 2;
    int m = rand() % (n * (n - 1) / 2) + 1;
    set<pair<int, int>> kek;
    vector<pair<int, int>> edges(m);
    for (int i = 0; i < m; ++i) {
      int a = rand() % (n - 1);
      int b = a + rand() % (n - a - 1) + 1;
      while (kek.count(make_pair(a, b))) {
        a = rand() % (n - 1);
        b = a + rand() % (n - a - 1) + 1;
      }
      kek.emplace(a, b);
      edges[i] = make_pair(a, b);
    }

    auto ans1 = solve(n, edges);
    auto ans2 = solve_dumb(n, edges);
    if (ans1 != ans2) {
      cerr << "BUG!!!\n";
      cerr << m << ' ' << n << '\n';
      for (auto [a, b] : edges)
        cerr << a + 1 << ' ' << b + 1 << '\n';
      cerr << "wrong: ";
      cerr << ans1.first << ' ' << ans1.second << '\n';
      cerr << "right: ";
      cerr << ans2.first << ' ' << ans2.second << "\n\n";
    }
  }

#else  
  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);
  }
  auto [ans1, ans2] = solve(n, edges);
  cout << ans1 << ' ' << ans2 << '\n';
#endif
  return 0;
}