#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define len(x) (int)x.size()
#define all(x) x.begin(), x.end()
const ll INF = 1e18;
const int INFi = 1e9;

void rel(pair<int,int> &cur, pair<int, int> add) {
    if (cur.first == add.first) cur.second += add.second;
    else cur = max(cur, add);
}

void dfs(int v, vector<int> &used, vector<vector<int>> &g, vector<int> &t) {
    used[v] = 1;
    for (int to: g[v]) if (!used[to]) {
        dfs(to, used, g, t);
    }
    t.push_back(v);
}

bool comp(vector<int> c1, vector<int> c2) {
    return c1 == c2;
    int n = len(c1);
    vector<int> to(n, -1);
    for (int i = 0; i < n; ++i) {
        if (to[c1[i]] != -1 && to[c1[i]] != c2[i]) return false;
        to[c1[i]] = c2[i];
    }
    for (int i = 0; i < n; ++i) {
        c1[i] = to[c1[i]];
    }
    return c1 == c2;
//    return true;
}

vector<int> on_comp(vector<vector<int>> &g, vector<vector<int>> &gr) {
    int n = len(g);
    vector<int> used(n);
    vector<int> t;
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            dfs(i, used,g, t);
        }
    }
    reverse(all(t));
    used.assign(n, 0);
    vector<int> comp(n);
    int cur = 0;
    for (int i: t) {
        if (!used[i]) {
            vector<int> c;
            dfs(i, used,gr, c);
            for (auto v: c) {
                comp[v] = cur;
            }
            ++cur;
        }
    }
    return comp;
}

void solve() {
    int n, m, G;
    cin >> n >> m >> G;

    vector<pair<int, int>> edges;
    vector<vector<int>> g(n), gr(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        edges.emplace_back(a, b);
        g[a].push_back(b);
        gr[b].push_back(a);
    }

    auto st = on_comp(g, gr);

    pair<int, int> ans = {0, 1};

    for (int s = 0; s < (1 << m); ++s) {
        for (int i = 0; i < n; ++i) {
            g[i].clear();
            gr[i].clear();
        }
        int cnt = 0;
        for (int i = 0; i < m; ++i) {
            auto [v, u] = edges[i];
            if (1 & (s >> i)) {
                ++cnt;
                g[u].push_back(v);
                gr[v].push_back(u);
            } else {
                g[v].push_back(u);
                gr[u].push_back(v);
            }
        }

        if (cnt == 3) {
            int a = 5, b = 6;
        }

        if (comp(on_comp(g, gr), st)) {
            pair<int, int> cur = {cnt, 1};
            rel(ans, cur);
        }
    }

    cout << ans.first << ' ' << ans.second << '\n';
}

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

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt","w", stdout);
#endif

    int t = 1;
//    cin >> t;
    while(t--) {
        solve();
    }

    return 0;
}