//#pragma GCC optimize("O3,unroll-loops,inline")

#include <bits/allocator.h>

//#pragma GCC target("avx2,popcnt")

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
using ll = long long;
using ull = unsigned long long;

struct segtree {
    vector<int> tr;
    int n;
    segtree(int n) : n(n), tr(2 * n) {}
    void upd(int i, int x) {
        for (tr[i += n] = x; i >= 0; tr[i >>= 1] = max(tr[i], tr[i ^ 1]));
    }
    int get(int l, int r) {
        int ans = 0;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1)
                ans = max(ans, tr[l++]);
            if (~r & 1)
                ans = max(ans, tr[r--]);
        }
        return ans;
    }
};

struct fenwick {
    vector<int> t;
    int n;
    fenwick(int n) : n(n), t(n + 1) {}
    void upd(int i, int x) {
        for (++i; i <= n; i += i & -i) t[i] += x;
    }
    int get(int i) {
        int x = 0;
        for (++i; i > 0; i -= i & -i) x += t[i];
        return x;
    }
};

template<class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, const T &b) {
    if (b > a) {
        a = b;
        return true;
    }
    return false;
}

mt19937 rnd(228);

vector<int> c(vector<vector<int>> gr) {
    int n = gr.size();
    vector<int> c(n);
    for (int i = 0; i < n; ++i)
        for (int j : gr[i])
            c[i] |= 1 << j;
    for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i)
            for (int j : gr[i])
                c[i] |= c[j];
    vector<int> cc(n);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) {
            bool ok = (c[i] & (1 << j)) && (c[j] & (1 << i));
            if (ok)
                cc[i] |= 1 << j, cc[j] |= 1 << i;
        }
    return cc;
}

void solve() {
    int n, m, g;
    cin >> n >> m >> g;
    vector<pair<int, int>> e;
    for (int i = 0, u, v; i < m; ++i) {
        cin >> u >> v;
        --u, --v;
        e.push_back({u, v});
    }
    vector<vector<int>> gr(n);
    for (int i = 0; i < m; ++i)
        gr[e[i].first].push_back(e[i].second);
    auto cc = c(gr);
    int ans = 0, cnt = 0;
    for (int mask = 0; mask < (1 << m); ++mask) {
        bool bad = true;
        for (int mask2 = mask; mask2 > 0; mask2 = (mask2 - 1) & mask) {
            vector<vector<int>> gr(n);
            for (int i = 0; i < m; ++i)
                if (mask2 & (1 << i))
                    gr[e[i].second].push_back(e[i].first);
                else
                    gr[e[i].first].push_back(e[i].second);
            auto ccc = c(gr);
            if (ccc == cc)
                bad = false;
        }
        if (bad) {
            if (ans < __builtin_popcount(mask)) {
                ans = __builtin_popcount(mask);
                cnt = 0;
            }
            if (ans == __builtin_popcount(mask)) {
                ++cnt;
            }
        }
    }
    cout << ans << '\n' << cnt;
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int t = 1;
//     cin >> t;
    while (t--) solve();
//    cerr << fixed << setprecision(10) << clock() * 1.0 / CLOCKS_PER_SEC << '\n';
}
