#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using pii = pair<int, int>;
constexpr char nl = '\n';

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    const ll mod = 1e9 + 7;
    int n, m, gg;
    cin >> n >> m >> gg;
    vvi g(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    ll ans = 0, cnt = 1;
    for (int i = 0; i < n; ++i) {
        vi dp(n, false);
        queue<int> q;
        q.push(i);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v: g[u]) {
                if (dp[v] == 0) {
                    q.push(v);
                    dp[v] = dp[u] + 1;
                }
            }
        }
        for (int v: g[i]) {
            if (dp[v] >= 2) {
                ++ans;
            }
        }
    }
    cout << ans << ' ' << cnt;
}
