//#pragma GCC optimize("unroll-loops", "Ofast")
//#pragma GCC target("sse","sse2","avx","avx2")
#include <bits/stdc++.h>

//#define int long long
#define F first
#define S second
using namespace std;
int n, m;
vector<vector<int>> g, rg;
vector<pair<int, int>> e;
vector<int> top;
vector<bool> used;
vector<int> cmp;

void topsort(int v) {
    used[v] = 1;
    for (int i: g[v]) {
        if (!used[i]) {
            topsort(i);
        }
    }
    top.push_back(v);
}

int C;

void css(int v) {
    cmp[v] = C;
    for (int i: rg[v]) {
        if (cmp[i] == -1) {
            css(i);
        }
    }
}

set<vector<int>> getcss(int msk) {
    g.assign(n, {});
    rg.assign(n, {});
    used.assign(n, 0);
    top.clear();
    C = 0;
    cmp.assign(n, -1);
    for (int i = 0; i < m; ++i) {
        if ((1 << i) & msk) {
            g[e[i].S].push_back(e[i].F);
            rg[e[i].F].push_back(e[i].S);
        } else {
            g[e[i].F].push_back(e[i].S);
            rg[e[i].S].push_back(e[i].F);
        }
    }
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            topsort(i);
        }
    }
    reverse(top.begin(), top.end());
    for (int i: top) {
        if (cmp[i] == -1) {
            css(i);
            C++;
        }
    }
    map<int, vector<int>> ans;
    for (int i = 0; i < n; ++i) {
        ans[cmp[i]].push_back(i);
    }
    set<vector<int>> ss;
    for (auto [k, v]: ans) {
        ss.insert(v);
    }
    return ss;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int G;
    cin >> n >> m >> G;
    e.resize(m);
    for (int i = 0; i < m; ++i) {
        cin >> e[i].F >> e[i].S;
        e[i].F--;
        e[i].S--;
    }
    auto i = getcss(0);
    vector<int> suit;
    for (int j = 0; j < 1 << m; j++) {
        auto k = getcss(j);
        if (k == i) {
            suit.push_back(j);
        }
    }
    int mx = 0, cnt = 1;
    for (int j = 0; j < 1 << m; ++j) {
        set<int> s;
        for (int k: suit) {
            if ((k & ((1 << m) - 1 - j)) == 0) {
                s.insert(k & j);
            }
        }
        if (s.size() == 1) {
            int newel = __builtin_popcount(j);
            if (newel > mx) {
                mx = newel;
                cnt = 1;
            } else if (newel == mx) {
                cnt++;
            }
        }
    }
    cout << mx;
    cout << '\n';
    cout << cnt;
    return 0;
}
//не забудь сохранять коды!!!

