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

using namespace std;
using namespace __gnu_pbds;

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

const int N = 2e3 + 1;
const int mod = 1e9 + 7;

int add(int a, int b) {
    return a + b >= mod ? a + b - mod : a + b;
}
int sub(int a, int b) {
    return a - b < 0 ? a - b + mod : a - b;
}
int mult(int a, int b) {
    return a * 1ll * b % mod;
}
int bpow(int a, int b) {
    int ans = 1;
    while (b) {
        if (b & 1) ans = mult(ans, a);
        a = mult(a, a);
        b >>= 1;
    }
    return ans;
}

int can[N];
vector<int> find_comp(vector<vector<int>>& g, int n) {
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            can[i] = 0;
        }
    }

    vector<int> from(n + 1);
    for (int i = 1; i <= n; ++i) {
        queue<int> q;
        q.push(i);
        can[i] = 1 << i;

        while (!q.empty()) {
            int v = q.front();
            q.pop();

            for (auto& u: g[v]) {
                if (!(can[i] >> u & 1)) {
                    can[i] |= 1 << u;
                    q.push(u);
                }
            }
        }
    }

    vector<int> used(n + 1);
    vector<int> comp;

    for (int i = 1; i <= n; ++i) {
        if (used[i]) continue;
        int cm = 1 << i;
        int fm = can[i];
        used[i] = 1;

        for (int j = 1; j <= n; ++j) {
            if (!used[j] && (fm >> j & 1) && (can[j] & cm) == cm) {
                fm |= can[j];
                cm |= 1 << j;
                used[j] = 1;
            }
        }

        comp.push_back(cm);
    }

    sort(comp.begin(), comp.end());
    return comp;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);

    int n, m, G;
    cin >> n >> m >> G;
    
    vector<pair<int, int>> edge;
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        edge.push_back({u, v});
    }

    vector<int> start = find_comp(g, n);

    if (G < 3) {
        int mx = 0, mxc = 0;
        for (int mask = 0; mask < (1 << m); ++mask) {
            bool can = 0;
            for (int sub = mask; sub; sub = (sub - 1) & mask) {
                if (sub == 0) continue;
                
                vector<vector<int>> fg(n + 1);
                for (int i = 0; i < m; ++i) {
                    if (sub >> i & 1) {
                        fg[edge[i].second].push_back(edge[i].first);
                    } else {
                        fg[edge[i].first].push_back(edge[i].second);
                    }
                }

                if (start == find_comp(fg, n)) {
                    can = 1;
                    break;
                }
            }

            if (!can) {
                if (__builtin_popcount(mask) == mx) {
                    mxc++;
                } else if (__builtin_popcount(mask) > mx) {
                    mx = __builtin_popcount(mask);
                    mxc = 1;
                }
            }
        }
        cout << mx << "\n" << mxc << "\n";
    } else {
        return 0;
    }

    return 0;
}
