#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define all(x) x.begin(), x.end()
#define ff first
#define ss second

using namespace std;
using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
using pii = pair<int, int>;

constexpr int MAXN = 2004;

vector<int> g[MAXN];

int fard = 0;

void dfs(int v, int d) {
    fard = max(fard, d);
    for (int child : g[v]) {
        dfs(child, d + 1);
    }
}

signed main() {
    int n, m, gr;
    cin >> n >> m >> gr;
    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);
    }
    int sub = 0;
    for (int i = 0; i < n; ++i) {
        fard = 0;
        dfs(i, 0);
        sub = max(sub, fard);
    }
    cout << (m - sub) << endl;
    cout << 1 << endl;
}
