#pragma GCC optimize("03")
#include <iostream>
#include <set>
#include <vector>
#include <random>
#include <iomanip>
//#include <fstream>
#include <algorithm>
#include <map>
#include <unordered_set>
#include <unordered_map>
#pragma GCC target("avx2")
#define int long long
const int INF = 1e7;
const int N = 3e5 + 1;
using namespace std;
void dfs(vector<vector<int>>& g, vector<bool>& used, vector<int>& top, int u) {
    used[u] = true;
    for (auto v : g[u]) {
        if (used[v]) continue;
        dfs(g, used, top, v);
    }
    top.push_back(u);
}
void dfs2(vector<vector<int>>& g, vector<int>& color, int u, int col) {
    color[u] = col;
    for (auto v : g[u]) {
        if (color[v] != 0) continue;
        dfs2(g, color, v, col);
    }
}
vector<vector<int>> get_colors(vector<vector<int>> g, vector<vector<int>>& g2, int n, int m) {
    vector<bool> used(n);
    vector<int> top;
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            dfs(g, used, top, i);
        }
    }
    reverse(top.begin(), top.end());
    vector<int> colors(n);
    int col = 1;
    for (auto i : top) {
        if (colors[i] == 0) {
            dfs2(g2, colors, i, col++);
        }
    }
    vector<vector<int>> css(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (colors[i] == colors[j]) {
                css[i].push_back(j);
            }
        }
    }
    return css;
}
signed main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m, tp;
    cin >> n >> m >> tp;
    vector<vector<int>> g(n);
    vector<vector<int>> g2(n);
    vector<pair<int, int>> edg;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        edg.push_back({ u,v });
        g[u].push_back(v);
        g2[v].push_back(u);
    }
    vector<vector<int>> css = get_colors(g, g2, n, m);
    int H = (1 << m);
    int size = 0, cur = 1;
    vector<bool> bad(H);
    for (int k = 1; k < H; k++) {
        int sm = k;
        vector<vector<int>> g3(n), g4(n);
        for (int j = 0; j < m; j++) {
            if ((1 << j) & sm) {
                g4[edg[j].first].push_back(edg[j].second);
                g3[edg[j].second].push_back(edg[j].first);
            }
            else {
                g3[edg[j].first].push_back(edg[j].second);
                g4[edg[j].second].push_back(edg[j].first);
            }
        }
        vector<vector<int>> cs2 = get_colors(g3, g4, n, m);
        bool equ = true;
        vector<bool> gd(n);
        for (int j = 0; j < n; j++) {
            if (gd[j]) continue;
            if (cs2[j].size() != css[j].size()) {
                equ = false;
                break;
            }
            for (int k = 0; k < cs2[j].size(); k++) {
                if (cs2[j][k] != css[j][k]) {
                    equ = false;
                    break;
                }
                gd[cs2[j][k]] = true;
            }
            if (!equ) break;
        }
        if (equ) {
            bad[k] = true;
        }
    }
    for (int i = 1; i < H; i++) {
        int sz = 0;
        for (int j = 0; j < m; j++) {
            if (i & (1 << j)) {
                sz++;
                int xr = i ^ (1 << j);
                if (bad[xr]) {
                    bad[i] = true;
                }
            }
        }
        if (!bad[i]) {
            if (size < sz) {
                size = sz;
                cur = 1;
            }
            else if (size == sz) {
                cur++;
            }
        }
    }
    cout << size << "\n" << cur << '\n';
}