#ifdef LOCAL
#define _GLIBCXX_DEBUG
#define debug(x) cerr << __LINE__ << ": " << (#x) << " = " << (x) << endl
#else
#define debug(...) 42
#endif

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef __int128 LL;
#define all(x) (x).begin(), (x).end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T>
istream &operator >>(istream &in, vector<T> &a) {
    for (auto &elem : a) {
        in >> elem;
    }
    return in;
}

template<typename T>
ostream &operator <<(ostream &out, const vector<T> &a) {
    for (const auto &elem : a) {
        out << elem << ' ';
    }
    return out;
}

int n, m;
vector<pair<int, int>> edges;
vector<vector<int>> g, rg;

void top_sort(int v, vector<bool> &used, vector<int> &order) {
    used[v] = true;
    for (int u : g[v]) {
        if (!used[u]) {
            top_sort(u, used, order);
        }
    }
    order.push_back(v);
}

void css(int v, vector<int> &color) {
    for (int u : rg[v]) {
        if (!color[u]) {
            color[u] = color[v];
            css(u, color);
        }
    }
}

vector<int> get(const int &mask) {
    g.assign(n + 1, vector<int>());
    rg.assign(n + 1, vector<int>());
    for (int i = 0; i < m; ++i) {
        const auto &[u, v] = edges[i];
        if (!(mask & (1 << i))) {
            g[u].push_back(v);
            rg[v].push_back(u);
        } else {
            g[v].push_back(u);
            rg[u].push_back(v);
        }
    }
    vector<bool> used(n + 1);
    vector<int> order;
    for (int v = 1; v <= n; ++v) {
        if (!used[v]) {
            top_sort(v, used, order);
        }
    }
    ranges::reverse(order);
    vector<int> color(n + 1);
    int cur_color = 1;
    for (int v : order) {
        if (!color[v]) {
            color[v] = cur_color++;
            css(v, color);
        }
    }
    return color;
}

void solve() {
    auto color = get(0);
    vector<bool> bad(1 << m);
    int res = 0, cnt = 1;
    for (int mask = 1; mask < (1 << m); ++mask) {
        bad[mask] = true;
        {
            const auto &cur = get(mask);
            for (int i = 1; i < n && bad[mask]; ++i) {
                for (int j = i + 1; j <= n; ++j) {
                    if ((color[i] == color[j]) != (cur[i] == cur[j])) {
                        bad[mask] = false;
                        break;
                    }
                }
            }
        }
        if (bad[mask]) { continue; }
        int cur_res = 0;
        for (int i = 0; i < m; ++i) {
            if (mask & (1 << i)) {
                bad[mask] = bad[mask - (1 << i)];
                if (bad[mask]) { break; }
                cur_res++;
            }
        }
        if (!bad[mask]) {
            if (cur_res > res) {
                res = cur_res;
                cnt = 1;
            } else if (cur_res == res) {
                cnt++;
            }
        }
    }
    cout << res << ' ' << cnt << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int trash;
    cin >> n >> m >> trash;
    edges.resize(m);
    for (auto &[u, v] : edges) {
        cin >> u >> v;
    }
    solve();
}