#include <bits/extc++.h>
using namespace std;
#define int long long
const int MAX_N = 2007;
vector<int> g[MAX_N];
void solve(){
    int n, m, G;
    cin >> n >> m >> G;
    set<int> st;
    for(int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        if(u + 1 != v && (u != n || v != 1)){
            st.insert(v);
            st.insert(u);
        }
    }
    cout << n - max((int)1, (int)st.size()) - 1 << "\n" << n << "\n";
}
signed main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int tim = clock();
    int tt =  1;
    //cin >> tt;
    while(tt--){
        solve();
    }
    //cout << (long double)(clock() - tim) / CLOCKS_PER_SEC << "\n";
}
/*
5 4 0
1 2
2 3
3 4
4 5
 */