#ifndef LOCAL
#pragma GCC optimize("O3")
#endif

#include <bits/extc++.h>

using namespace std;


using namespace __gnu_pbds;
using oset = tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
using ll = long long;
const ll nMax = 200 + 228;
const ll mod = 1e9+7;
vector<int> g[nMax];
vector<int> gr[nMax];
bitset<20> used;
vector<int> topsort;
int comp[nMax],compCnt;
void dfs (int v, int p){
    used[v]=true;
    for(auto u : g[v]){
        if(used[u])continue;
        dfs(u,p);
    }
    topsort.push_back(v);
};
void dfs2 (int v){
    comp[v]=compCnt;
    for(auto u : gr[v]){
        if(comp[u])continue;
        dfs2(u);
    }
};
ll n,m,gg;
vector<int> getcomps(){
    used.reset();
    topsort.clear();
    for(int i=1;i<=n;i++){
        comp[i]=0;
        if(used[i])continue;
        dfs(i,i);
        comp[i]=0;
    }
    std::reverse(topsort.begin(), topsort.end());

    for(auto u : topsort){
        if(comp[u])continue;
        compCnt++;
        dfs2(u);
    }
    vector<int> res;
    for(int i=1;i<=n;i++)res.push_back(comp[i]);
    map<int,int> code;
    for(int i=0;i<n;i++){
        if(code[res[i]]==0)code[res[i]]=code.size();
        res[i]=code[res[i]];
    }
    return res;
}
bool bad[1 << 20];
void solve() {

    cin >> n >> m >> gg;
    vector<pair<int,int>> edges;
    for(int i=0;i<m;i++){
        int u,v;
        cin >> u >> v;
        edges.push_back({u,v});
        g[u].push_back(v);
        gr[v].push_back(u);
    }
    auto def = getcomps();

    for(int i=0; i < (1 << m); i++){
        for(int j=1;j<=n;j++)g[j].clear();
        for(int j=1;j<=n;j++)gr[j].clear();
        for(int j=0;j<m;j++){
            if((i & (1<<j)) == 0)g[edges[j].first].push_back(edges[j].second);
            else g[edges[j].second].push_back(edges[j].first);
            if((i & (1<<j)))gr[edges[j].first].push_back(edges[j].second);
            else gr[edges[j].second].push_back(edges[j].first);
        }
        if(getcomps()==def)bad[i]=true;
    }
    int maxo =0;
    int anso = 0;
    for(int i =0;i<(1 << m); i++){
        int cnt =0;
        for(int j = i; j; j = (j-1) & i){
            if(bad[j])cnt++;
        }
        if(!cnt){
            if(maxo < __builtin_popcount(i))
                anso = 0;
            if(maxo > __builtin_popcount(i))continue;
            maxo = max(maxo, __builtin_popcount(i));

            anso++;
        }
    }
    cout << maxo << ' ' << anso;
}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    cin.tie(0)->sync_with_stdio(0);
    int tt = 1;
    //cin >> tt;
    while (tt--)solve();
}