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

using namespace std;

#define ll int

vector<vector<ll>> gr;
vector<vector<ll>> gr1;
vector<bool> used;
vector<ll> t;

void dfs(ll v) {
    used[v] = true;
    for (auto elem : gr[v]) {
        if (!used[elem]) {
            dfs(elem);
        }
    }
    t.push_back(v);
}

vector<ll> answer;
ll min1 = (ll)1e9;

void dfs1(ll v, ll k) {
    used[v] = true;
    answer[v] = k;
    min1 = min(min1, v);
    for (auto elem : gr1[v]) {
        if (!used[elem]) {
            dfs1(elem, k);
        }
    }
}

void f(vector<pair<ll, ll>> &a, ll n) {
    gr.assign(n, vector<ll>());
    gr1.assign(n, vector<ll>());
    for (auto elem : a) {
        gr[elem.first].push_back(elem.second);
        gr1[elem.second].push_back(elem.first);
    }
    t.clear();
    used.assign(n, false);
    for (ll i = 0; i < n; i++) {
        if (!used[i]) {
            dfs(i);
        }
    }
    reverse(t.begin(), t.end());
    used.assign(n, false);
    answer.assign(n, 0);
    ll k = 0;
    vector<ll> k1;
    for (auto elem : t) {
        if (!used[elem]) {
            min1 = (ll)1e9;
            dfs1(elem, k);
            k1.push_back(min1);
            k++;
        }
    }
    for (ll i = 0; i < answer.size(); i++) {
        answer[i] = k1[answer[i]];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n, m, g;
    cin >> n >> m >> g;
    vector<pair<ll, ll>> a(m);
    for (ll i = 0; i < m; i++) {
        cin >> a[i].first >> a[i].second;
        a[i].first--;
        a[i].second--;
    }
    vector<ll> dp(1 << m);
    f(a, n);
    vector<ll> answer3 = answer;
    for (ll i1 = 0; i1 < (1 << m); i1++) {
        vector<pair<ll, ll>> a2;
        ll x = i1;
        ll y = 0;
        vector<ll> c;
        for (ll i = 0; i < m; i++) {
            if (x % 2 == 0) {
                a2.push_back(a[i]);
                c.push_back(i);
            } else if (x % 2 == 1) {
                a2.push_back({a[i].second, a[i].first});
                y += (1 << i);
            }
            x = x / 2;
        }
        f(a2, n);
        if (answer == answer3) {
            for (ll i2 = 0; i2 < (1 << c.size()); i2++) {
                ll x2 = i2;
                ll y1 = y;
                for (ll j = 0; j < c.size(); j++) {
                    if (x2 % 2 == 1) {
                        y1 += (1 << c[j]);
                    }
                    x2 = x2 / 2;
                }
                dp[y1]++;
            }
        }
    }
    ll answer = 0;
    ll answer1 = 0;
    for (ll i1 = 0; i1 < (1 << m); i1++) {
        if (dp[i1] == 1) {
            ll x = i1;
            ll k1 = 0;
            for (ll i = 0; i < m; i++) {
                k1 += x % 2;
                x = x / 2;
            }
            if (answer < k1) {
                answer = k1;
                answer1 = 1;
            } else if (answer == k1) {
                answer = k1;
                answer1++;
            }
        }
    }
    cout << answer << '\n';
    cout << answer1;
}