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

using namespace std;

#define ll long long

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<vector<ll>> answer;

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

vector<vector<ll>> 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.clear();
    ll k = 0;
    for (auto elem : t) {
        if (!used[elem]) {
            answer.push_back(vector<ll>());
            dfs1(elem, k);
            k++;
        }
    }
    for (ll i = 0; i < k; i++) {
        sort(answer[i].begin(), answer[i].end());
    }
    sort(answer.begin(), answer.end());
    return answer;
}

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);
    ll x1 = 1;
    for (ll i = 0; i < m; i++) {
        x1 *= 3;
    }
    for (ll i1 = 0; i1 < x1; i1++) {
        vector<pair<ll, ll>> a1;
        vector<pair<ll, ll>> a2;
        ll x = i1;
        ll y = 0;
        for (ll i = 0; i < m; i++) {
            a1.push_back(a[i]);
            if (x % 3 == 1) {
                a2.push_back(a[i]);
                y += (1 << i);
            } else if (x % 3 == 2) {
                a2.push_back({a[i].second, a[i].first});
                y += (1 << i);
            } else {
                a2.push_back(a[i]);
            }
            x = x / 3;
        }
        vector<vector<ll>> answer1 = f(a1, n);
        vector<vector<ll>> answer2 = f(a2, n);
        if (answer1 == answer2) {
            dp[y]++;
        }
    }
    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;
}