#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct dsu {
    int n;
    vector<int> sizes, par;

    dsu(const int _n) {
        n = _n;
        sizes.resize(n, 1);
        par.resize(n);
        iota(par.begin(), par.end(), 0);
    }

    int get(int x) {
        return x == par[x] ? x : par[x] = get(par[x]);
    }

    bool merge(int x, int y) {
        x = get(x), y = get(y);
        if (x == y) {
            return false;
        }
        if (sizes[x] > sizes[y]) {
            swap(x, y);
        }
        sizes[y] += sizes[x];
        par[x] = y;
        return true;
    }
};

int main() {
#ifdef home
    freopen("f.in", "r", stdin);
    freopen("f.out", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, usls;
    cin >> n >> m >> usls;
    vector<int> ev(m), eu(m);
    for (int i = 0; i < m; i++) {
        int v, u;
        cin >> v >> u;
        v--, u--;
        ev[i] = v, eu[i] = u;
    }
    cout << n - 1 << '\n';
    cout << "-1\n";
    return 0;
    auto dfs = [&](auto &&self, int v, const vector<vector<int>> &g, vector<bool> &used) -> void {
        used[v] = true;
        for (auto &u: g[v]) {
            if (!used[u]) {
                self(self, u, g, used);
            }
        }
    };
    auto check = [&](const vector<vector<int>> &g) {
        dsu meow(n);
        vector<vector<bool>> can(n, vector<bool>(n, false));
        for (int v = 0; v < n; v++) {
            dfs(dfs, v, g, can[v]);
        }
        for (int v = 0; v < n; v++) {
            for (int u = 0; u < n; u++) {
                if (can[v][u] && can[u][v]) {
                    meow.merge(v, u);
                }
            }
        }
        unordered_map<int, vector<int>> flex;
        for (int v = 0; v < n; v++) {
            flex[meow.get(v)].emplace_back(v);
        }
        vector<vector<int>> ans;
        for (auto &[_, cur]: flex) {
            ans.emplace_back(cur);
        }
        ranges::sort(ans);
        return ans;
    };
    vector<vector<int>> cat;
    {
        vector<vector<int>> g(n);
        for (int i = 0; i < m; i++) {
            g[ev[i]].emplace_back(eu[i]);
        }
        cat = check(g);
    }
    int ans = 0, cnt = 0;
    for (int mask = 0; mask < (1 << m); mask++) {
        int shit = 0;
        for (int submask = mask;; submask = (submask - 1) & mask) {
            vector<vector<int>> g(n);
            for (int i = 0; i < m; i++) {
                int v = ev[i], u = eu[i];
                if ((mask >> i) & 1) {
                    if ((submask >> i) & 1) {
                        g[v].emplace_back(u);
                    } else {
                        g[u].emplace_back(v);
                    }
                } else {
                    g[v].emplace_back(u);
                }
            }
            if (check(g) == cat) {
                shit++;
            }
            if (shit > 1) {
                break;
            }
            if (submask == 0) {
                break;
            }
        }
        if (shit == 1) {
            int cand = __builtin_popcount(mask);
            if (cand > ans) {
                ans = cand;
                cnt = 0;
            }
            if (cand == 3) {
                cout << mask << endl;
            }
            if (cand == ans) {
                cnt++;
            }
        }
    }
    cout << ans << '\n' << cnt << '\n';
    return 0;
}
