#ifdef LOCAL
#define _GLIBCXX_DEBUG
#else
#pragma GCC optimize("O3")
#endif

#include <bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) int((x).size())
using pii = pair<int, int>;
using pll = pair<int64_t, int64_t>;
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
#define MAX_FAC 5000
const ll MOD = 1e9 + 7;

ll binpow(ll x, int p) {
    ll res = 1;
    while (p) {
        if (p % 2) res = res * x % MOD;
        x = x * x % MOD;
        p /= 2;
    }
    return res;
}

ll inv(ll x) {
    return binpow(x, MOD - 2);
}

vector<ll> fac(MAX_FAC);
vector<ll> inv_fac(MAX_FAC);
vector<vector<int>> g;
vector<vector<int>> full_g;
vector<bool> marked;

ll c(ll n, ll k) {
    return fac[n] * inv_fac[k] % MOD * inv_fac[n - k] % MOD;
}

void mark_component(int v) {
    marked[v] = true;
    for (int u : full_g[v]) {
        if (!marked[u]) {
            mark_component(u);
        }
    }
}

void solve() {
    int n, m, G;
    cin >> n >> m >> G;
    g.resize(n);
    marked.resize(n);
    full_g.resize(n);
    vector<int> incoming(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[u].push_back(v);
        full_g[v].push_back(u);
        full_g[u].push_back(v);
        incoming[v]++;
    }
    int cnt_components = 0;
    for (int i = 0; i < n; i++) {
        if (!marked[i]) {
            mark_component(i);
            cnt_components++;
        }
    }
    ll ans_amount = n - 1, ans_ways = 1;
    // for (int i = 1; i < n; i++) {
    //     if (incoming[i] == 0 && g[i].empty()) {
    //         ans_amount++;
    //     }
    // }
    cout << ans_amount << ' ' << ans_ways << '\n';
    // cout << m - (n - 1) << ' ' << c(m, m - (n - 1)) << '\n';
}

signed main() {
    fac[0] = 1;
    for (int i = 1; i < MAX_FAC; i++) {
        fac[i] = fac[i - 1] * i;
    }
    for (int i = 0; i < MAX_FAC; i++) {
        inv_fac[i] = inv(fac[i]);
    }
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    while (t--) solve();
}