#ifdef ONPC
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using i128 = __int128_t;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

mt19937_64 rng(chrono::steady_clock().now().time_since_epoch().count());

const int mod = 1e9 + 7;

vector<set<int>> ig, g;
vector<vector<int>> cg;
vector<vector<int>> ng;

template<typename T>
void topsort(int v, vector<int>& used, vector<int>& ts, vector<T>& g) {
    used[v] = 1;
    for (auto u : g[v]) {
        if (used[u]) continue;
        topsort(u, used, ts, g);
    }
    ts.push_back(v);
}

template<typename T>
void comp_dfs(int v, int cur, vector<int>& comps, vector<T> g) {
    comps[v] = cur;
    for (auto u : g[v]) {
        if (comps[u] != -1) continue;
        comp_dfs(u, cur, comps, g);
    }
}

vector<int> comps(vector<set<int>>& g, vector<set<int>>& ig) {
    int n = g.size();
    vector<int> res(n, -1);
    vector<int> ts, used(n, 0);
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            topsort(i, used, ts, g);
        }
    }
    reverse(ts.begin(), ts.end());

    int color = 0;
    for (int i = 0; i < n; i++) {
        if (res[ts[i]] == -1) continue;
        comp_dfs(ts[i], color, res, ig);
        color++;
    }

    return res;
}

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

    int n, m, group;
    cin >> n >> m >> group;
    g.resize(n);
    cg.resize(n);
    ig.resize(n);
    vector<array<int, 2>> e;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[u].insert(v);
        ig[v].insert(u);
        e.push_back({u, v});
    }

    auto change_edge = [&](int u, int v) {
        g[u].erase(v);
        g[v].insert(u);
        ig[v].erase(u);
        ig[u].insert(v);
    };

    int cnt = 0;
    vector<int> start_c = comps(g, ig);
    for (auto [u, v] : e) {
        change_edge(u, v);
        vector<int> cur_c = comps(g, ig);
        change_edge(v, u);

        cnt += (cur_c == start_c);
    }

    int can_e = cnt;
    ll ans = 1;

    if (cnt == n) can_e--, ans *= n;

    cout << can_e << '\n';
    cout << ans << '\n';

    return 0;
}
