#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<stack>
#include<queue>
#include<deque>
#include<bitset>
#include<iomanip>

using namespace std;
using ll = long long int;
using ld = long double;

vector<int> ts, color;
vector<bool> used;

vector<vector<int>> graph1, rgraph1;

void dfs(int v) {
    used[v] = true;
    for (auto elem : graph1[v]) {
        if (!used[elem]) {
            dfs(elem);
        }
    }
    ts.push_back(v);
}

void dfs1(int v, int col) {
    color[v] = col;
    for (auto elem : rgraph1[v]) {
        if (color[elem] == -1) {
            dfs1(elem, col);
        }
    }
}

int getcomps() {
    ts.clear();
    used.clear();
    color.clear();
    int n = graph1.size();
    used.resize(n, false);
    color.resize(n, -1);
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            dfs(i);
        }
    }
    reverse(ts.begin(), ts.end());
    int cnt = 0;
    for (auto elem : ts) {
        if (color[elem] == -1) {
            dfs1(elem, cnt++);
        }
    }
    return cnt;
} 

void solve() {
    int n, m, g;
    cin >> n >> m >> g;
    vector<vector<int>> graph;
    vector<pair<int, int>> edges;
    graph.resize(n);
    edges.resize(m);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        u -= 1, v -= 1;
        graph[u].push_back(v);
        edges[i] = {u, v};
    }
    int mx = 0, kol = 0;
    int kolkomp = 0;
    for (int i = 0; i < (1 << m); ++i) {
        graph1.clear();
        graph1.resize(n);
        rgraph1.clear();
        rgraph1.resize(n);
        for (int j = 0; j < n; ++j) {
            for (auto elem: graph[j]) {
                graph1[j].push_back(elem);
                rgraph1[elem].push_back(j);
            }
        }
        for (int j = 0; j < m; ++j) {
            if ((i >> j) & 1) {
                graph1[edges[j].second].push_back(edges[j].first);
                rgraph1[edges[j].first].push_back(edges[j].second);
            }
        }
        int KOL = getcomps();
        if (i == 0) {
            kolkomp = KOL;
        }
        if (KOL == kolkomp) {
            int bits = __builtin_popcount(i);
            if (bits > mx) {
                mx = bits;
                kol = 1;
            } else if (bits == mx) {
                kol++;
            }
        }
    }
    cout << mx << "\n" << kol;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt = 1;
    while (tt--) {
        solve();
    }
}