//#define _GLIBCXX_DEBUG
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")

#include<bits/stdc++.h>
//#include<ext/pb_ds/tree_policy.hpp>
//#include<ext/pb_ds/assoc_container.hpp>
using ll = long long;
#define int ll
using namespace std;
//using namespace __gnu_pbds;
//mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
//mt19937 mt(52);
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int mod = 1000000007;
void dfs(int u, vector<int> &used, vector<vector<int>> &g, int col){
    used[u] = col;
    for(auto &v: g[u]) if(!used[v]) dfs(v, used, g, col);
}
void solve() {
    vector<int> ps(2001);
    ps[0] = 1;
    int n, m, group;
    cin >> n >> m >> group;
    if(group == 3){
        cout << m-n+1 << ' ' << 1; return;
    }
    vector<vector<int>> g(n), t(n);
    for(int i=0; i<m; ++i){
        int u, v;
        cin >> u >> v;
        --u; --v;
        g[u].push_back(v);
        if(u+1==v) t[u].push_back(v);
    }
    int col = 1;
    vector<int> used(n);
    for(int i=0; i<n ;++i){
        if(!used[i]){
            dfs(i, used, g, col);
            ++col;
        }
    }
    int ans = 0;
    for(int u=0; u<n; ++u){
        for(auto &v : g[u]) if(u+1 != v && used[u] == used[v]) ++ans;
    }
    cout << ans <<' '<< 1;
}


signed main(){
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    bool cfmode = !(42);
    if(cfmode){
        int t;
        cin >> t;
        while(t--){
            solve();
            cout << '\n';
        }
    } else solve();
}