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

using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ld = long double;
using o_set = tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>;

//find_by_order()
//order_of_key()

constexpr ll mod = 1e9 + 7;

int cur = 0, cur1 = 0;

struct T {
    int v, u;
};

vector<set<int>> g, g1;
vector<bool> used;
vector<int> color, color_check, pr;
vector<ll> cnt_cycle;

void dfs(int v) {
    used[v] = true;
    for (auto to : g[v]) {
        if (!used[to]) {
            dfs(to);
        }
    }
    pr.push_back(v);
}

void dfs1(int v) {
    color[v] = cur;
    for (auto to : g1[v]) {
        if (color[to] == -1) {
            dfs1(to);
        } else if (color[to] == color[v]) {
            cnt_cycle[color[v]]++;
        }
    }
}

void dfs_check(int v) {
    used[v] = true;
    for (auto to : g[v]) {
        if (!used[to]) {
            dfs_check(to);
        }
    }
    pr.push_back(v);
}

void dfs_check1(int v) {
    color_check[v] = cur1;
    for (auto to : g1[v]) {
        if (color_check[to] == -1) {
            dfs_check1(to);
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, gr;
    cin >> n >> m >> gr;
    g.resize(n);
    g1.resize(n);
    used.resize(n, false);
    color.resize(n, -1);
    cnt_cycle.resize(n + 1, 0);
    vector<ll> cnt_all(n + 1, 0);
    vector<T> e(m);
    ll cnt_comp = 0;
    for (int i = 0; i < m; i++) {
        cin >> e[i].v >> e[i].u;
        e[i].v--;
        e[i].u--;
        g[e[i].v].insert(e[i].u);
        g1[e[i].u].insert(e[i].v);
    }
    if (gr == 5 || gr == 6) {
        cout << n - 1 << '\n' << -1;
        return 0;
    }
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            dfs(i);
        }
    }
    for (int i = 0; i < int(pr.size()); i++) {
        if (color[pr[int(pr.size()) - i - 1]] == -1) {
            dfs1(pr[int(pr.size()) - i - 1]);
            cur++;
        }
    }
    for (int i = 0; i < m; i++) {
        if (color[e[i].v] == color[e[i].u]) {
            cnt_all[color[e[i].v]]++;
            continue;
        }
        cur1 = 0;
        pr.clear();
        used.clear();
        color_check.clear();
        color_check.resize(n, -1);
        used.resize(n, false);
        g[e[i].v].erase(e[i].u);
        g1[e[i].u].erase(e[i].v);
        g1[e[i].v].insert(e[i].u);
        g[e[i].u].insert(e[i].v);
        for (int j = 0; j < n; j++) {
            if (!used[j]) {
                dfs_check(j);
            }
        }
        for (int j = 0; j < int(pr.size()); j++) {
            if (color_check[pr[int(pr.size()) - j - 1]] == -1) {
                dfs_check1(pr[int(pr.size()) - j - 1]);
                cur1++;
            }
        }
        if (cur != cur1) {
            if (color[e[i].v] != color[e[i].u]) {
                cnt_comp++;
            }
        }
        g1[e[i].v].erase(e[i].u);
        g[e[i].u].erase(e[i].v);
        g[e[i].v].insert(e[i].u);
        g1[e[i].u].insert(e[i].v);
    }
    ll ans1 = cnt_comp, ans2 = 0;
    for (int i = 0; i <= n; i++) {
        ans1 += cnt_all[i] - cnt_cycle[i];
    }
    cout << ans1 << '\n';
    if (ans1 > 0) {
        ans2 = 1;
        if (cnt_comp > 0) {
            ans2 *= cnt_comp;
        }
        for (int i = 0; i <= n; i++) {
            if (cnt_all[i] - cnt_cycle[i] > 0) {
                ans2 *= (cnt_all[i] - cnt_cycle[i]);
            }
        }
    }
    cout << ans2;
    return 0;
}
