#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <deque>
#include <stack>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <fstream>
#include <bitset>
#include <string>

//#pragma GCC optimize("unroll-loops,inline,O2,O3,Ofast")
//#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,sse4,ssse3,abm,mmx,fma,popcnt,lzcnt")

using namespace std;

typedef long long ll;

ll INF = 1e18 + 9;

ll get(ll v, vector<ll> &p) {
    if (p[v] == -1) {
        return v;
    }
    return p[v] = get(p[v], p);
}

void merge(ll v1, ll v2, vector<ll> &p, vector<ll> &sz) {

    ll p1 = get(v1, p), p2 = get(v2, p);
    if (p1 == p2) {
        return;
    }

    if (sz[p1] > sz[p2]) {
        p[p2] = p1;
        sz[p1] += sz[p2];
    }
    else {
        p[p1] = p2;
        sz[p2] += sz[p1];
    }
}

void solve() {
    ll n, m, g, cnt = 0;
    cin >> n >> m >> g;

    vector<vector<ll>> h(n);
    vector<ll> p(n, -1), sz(n, 1);
    ll mn = INF;
    for (int i = 0;  i < m; i++) {
        ll x, y;
        cin >> x >> y;
        x--, y--;
        h[x].push_back(y);
        if (get(x, p) == get(y, p)) {
            mn = min(mn, abs(x - y));
        }
        merge(x, y, p, sz);
    }
    cout << max(m - mn, m / 2) << "  " << 0;
}

signed main() {

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll t = 1;
    //cin >> t;
    while (t--) {
        solve();
        cout << "\n";
    }

    return 0;
}
