#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> g;
vector<bool> us;

void dfs(int v, int p)
{
    if(us[v]) return;
    us[v] = 1;
    for(int u : g[v]) if(u != p){
        dfs(u, -1);
    }
}

signed main()
{
    int n, m, gr;
    cin >> n >> m >> gr;
    g.resize(n);
    vector<int> a, b;
    for(int i = 0; i < m; ++i){
        int u, v;
        cin >> u >> v;
        g[u - 1].push_back(v - 1);
        a.push_back(u - 1);
        b.push_back(v - 1);
    }
    int ans = 0, x = 0;
    vector<int> t(m);
    for(int i = 0; i < m; ++i){
        us.assign(n, 0);
        dfs(b[i], a[i]);
        if(!us[a[i]]){
            us.assign(n, 0);
            dfs(a[i], b[i]);
            if(us[b[i]]){
                t[i] = 1;
            }
            else t[i] = -1;
        }
    }
    for(int s = 0; s < (1<<m); ++s){
        int cnt = 0;
        bool f = 0;
        for(int i = 0; i < m; ++i)
            if((1&(s>>i)) && t[i] != 0) f = 1;
        if(f) continue;
        for(int i = 0; i < m; ++i) if(1&(s>>i)){
            g[b[i]].push_back(a[i]);
        }
        f = 1;
        for(int i = 0; i < m; ++i){
            if(1&(s>>i)){
                ++cnt;
                us.assign(n, 0);
                dfs(a[i], b[i]);
                if(us[b[i]]){
                    f = 0;
                    break;
                }
            }
            else if(t[i] == 1){
                ++cnt;
            }
        }
        if(f){
            if(cnt > ans){
                ans = cnt;
                x = 1;
            }
            else if(cnt == ans) ++x;
        }
        for(int i = 0; i < m; ++i) if(1&(s>>i)){
            g[b[i]].pop_back();
        }
    }
    cout << ans << endl << x << endl;
}