#include <bits/stdc++.h>

using namespace std;

void solve();

//#pragma GCC optimize("O3","Ofast","fastmath","unroll-loops")
//#pragma GCC target("avx2","sse4.2","bmi","lzcnt","popcnt")
int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

#define int long long
#define endl '\n'
const int N = 3e5 + 10, INF = 2e18, MOD = 1e9 + 7;
int cnt=0;
void dfs(int v,vector<vector<int>> &gr,vector<bool> &used,int p=-1){
    used[v]=true;
    for(auto to:gr[v]){
        if(!used[to]){
            dfs(to,gr,used,v);
        }
    }
}
void solve() {
    int n,m,g;
    cin>>n>>m>>g;
    vector<pair<int,int>> e(m);
    int ans=0;
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        u--;v--;
        e[i]={u,v};
    }
    for(auto [u,v]:e){
        if(v!=u+1)continue;
        bool ok=false;
        for(auto [f,s]:e){
            if(f==u && s==v)continue;
            if(min(f,s)<=u && max(f,s)>=u){
                ok=true;
                break;
            }
        }
        ans+=!ok;
    }
    cout<<ans<<endl;
    cout<<1<<endl;
}