#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;

#define ll long long 
vector<vector<pair<ll,ll>>>g;
vector<ll>used;
vector<ll>color;
vector<ll>q;
void dfs1(ll v){
    used[v]=1;
    for(auto to:g[v]){
        if(to.second==1){
            if(used[to.first]==0){
                dfs1(to.first);
            }
        }
    }
    q.push_back(v);
}
ll cv=0;
void dfs2(ll v){
    used[v]=1;
    color[v]=cv;
    for(auto to:g[v]){
        if(to.second==0){
            if(used[to.first]==0){
                dfs2(to.first);
            } 
        }
    }
}

int main() {
    ios_base::sync_with_stdio();
    cin.tie(0), cout.tie(0);
    ll n,m,gg;
    cin>>n>>m>>gg;vector<pair<ll,ll>>r;
    g.resize(n);
    for(ll i=0 ; i< m; i++){
        ll a,b;
        cin>>a>>b;
        a--;
        b--;
        r.push_back({a,b});
        g[a].push_back({b,1});
        g[b].push_back({a,0});
    }
    ll cnt=0;
    ll mx=0;
    vector<vector<ll>>all;
    vector<ll>bad;
    for(ll mask=0;mask<(1<<m);mask++){
        if(mask==0){
            used.assign(n,0);
            q.clear();
            for(ll i=0 ; i< n;i++){
                if(used[i]==0){
                  dfs1(i);
                }
            }
            reverse(q.begin(),q.end());
            used.assign(n,0);
            color.assign(n,0);
            cv=1;
            for(ll i=0 ; i< n;i++){
                if(used[q[i]]==0){
                    dfs2(q[i]);
                    cv++;
                }
            }
            vector<vector<ll>>all2;
            for(ll i=1; i<cv;i++){
                vector<ll>h;
                for(ll j=0 ;j < color.size();j++){
                    if(color[j]==i){
                        h.push_back(j);
                    }
                }
                all2.push_back(h);
            }
            sort(all2.begin(),all2.end());
            all=all2;
            continue;
        }
        ll e=0;
        for(ll j=0; j< m;j++){
            if((mask&(1<<j))!=0){
                e++;
                for(ll k=0 ;k < g[r[j].first].size();k++){
                    if(g[r[j].first][k].first==r[j].second){
                        g[r[j].first][k].second=0;
                    }
                }
                for(ll k=0 ;k < g[r[j].second].size();k++){
                    if(g[r[j].second][k].first==r[j].first){
                        g[r[j].second][k].second=1;
                    }
                }
            }
        }
        used.assign(n,0);
        q.clear();
        for(ll i=0 ; i< n;i++){
            if(used[i]==0){
                dfs1(i);
            }
        }
        reverse(q.begin(),q.end());
        used.assign(n,0);
        color.assign(n,0);
        cv=1;
        for(ll i=0 ; i< n;i++){
            if(used[q[i]]==0){
                dfs2(q[i]);
                cv++;
            }
        }
        vector<vector<ll>>all2;
            for(ll i=1; i<cv;i++){
                vector<ll>h;
                for(ll j=0 ;j < color.size();j++){
                    if(color[j]==i){
                        h.push_back(j);
                    }
                }
                all2.push_back(h);
            }
            sort(all2.begin(),all2.end());
        if(all2 == all){
           bad.push_back(mask);
        }
        for(ll j=0; j< m;j++){
            if((mask&(1<<j))!=0){
                for(ll k=0 ;k < g[r[j].first].size();k++){
                    if(g[r[j].first][k].first==r[j].second){
                        g[r[j].first][k].second=1;
                    }
                }
                for(ll k=0 ;k < g[r[j].second].size();k++){
                    if(g[r[j].second][k].first==r[j].first){
                        g[r[j].second][k].second=0;
                    }
                }
            }
        }
    }mx=0;
    cnt=0;
    ll ff=0;
    ll MX=1e6;
    for(ll mask=0;mask<(1<<m);mask++){
        ll e=0;
                    ll y=mask;
        while (y!=0)
        {
            y-=(y&(-y));
            e++;
        }
        
            if(e<mx){
                continue;
            }
        ll u=1;
        for(ll j=0; j < bad.size();j++){
            ff++;
            if(ff>=MX){
                break;
            }
            if((mask&bad[j])==bad[j]){
                u=0;
                break;
            }
        }
        if(ff>=MX){
            break;
        }
        if(u==1){
            ll e=0;
            for(ll j=0; j< m;j++){
                if((mask&(1<<j))!=0){
                    e++;
                }
            }
            if(e>mx){
                mx=e;
                cnt=1;
            }else{
                if(mx==e){
                    cnt++;
                }
            }
        }
    }
    cout<<mx<<endl;
    cout<<cnt<<endl;
}
