#include<bits/stdc++.h>
//#pragma GCC target("avx2")
#define int long long
#define F first
#define S second

using namespace std;

const int N = 3000+10;

vector<int> g[N], g_ans[N], g_ob[N];

vector<int> g1[N], g_ob1[N];

vector<pair<int, int>> d[N];

int comp[N][N], cl[N], fl[N][N], cnt = 0;

int kol[N];

bool us[N];

void dfs2(int v)
{
    us[v] = 1;
    cnt++;
//    cout<<"--->"<<v<<endl;
    for(auto i:g1[v])
    {
        if(us[i] || fl[v][i] == 2) continue;
        dfs2(i);
    }
    for(auto i:g_ob1[v])
    {
        if(us[i] || !fl[v][i]) continue;
        dfs2(i);
    }
}

bool dfs1(int v, int u, pair<int ,int> e)
{
    if(us[v]) return 0;
    us[v] = 1;
    bool ok = bool(v == u);
    if(ok)
        return 1;
    for(auto i:g_ob[v])
    {
        if(pair<int, int>{v, i} == e || pair<int, int>{i, v} == e)
            continue;
        ok |= dfs1(i, u, e);
        if(ok) return 1;
    }
    return ok;
}

void dfs(int v, int u)
{
    us[v] = 1;
    comp[u][v] = 1;
    for(auto i:g[v])
    {
        if(us[i]) continue;
        dfs(i, u);
    }
}

void dfs_ans(int v, int u)
{
    cl[v] = u;
    kol[u]++;
    for(auto i:g_ans[v])
    {
        if(cl[i]) continue;
        dfs_ans(i, u);
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    int n, m, ge;
    cin>>n>>m>>ge;
    vector<pair<int, int>> v;
    int n1 = n;
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        cin>>x>>y;
        g[x].push_back(y);
//        g_ob[y].push_back(x);
        v.push_back({x, y});
    }
    for(int i = 1; i <= n; i++)
    {
        dfs(i, i);
        fill(us, us+n+10, 0ll);
    }
    for(int i = 1; i <= n; i++)
        for(int j = i+1; j <= n; j++)
            if(comp[i][j] && comp[j][i])
                g_ans[i].push_back(j), g_ans[j].push_back(i);
    int tim = 1;
    for(int i = 1; i <= n; i++)
    {
        if(!cl[i]) dfs_ans(i, tim);
        tim++;
    }
    int ans = 0;
    vector<pair<int, int>> v1;
    map<pair<int, int>, int> mp;
    for(auto i:v)
    {
        if(cl[i.F] != cl[i.S] && !mp[{cl[i.F], cl[i.S]}])
            g_ob[cl[i.S]].push_back(cl[i.F]), v1.push_back({cl[i.F], cl[i.S]});
        else
            d[cl[i.F]].push_back({i.F, i.S});
        mp[{cl[i.F], cl[i.S]}]++;
        if(mp[{cl[i.F], cl[i.S]}] > 1)
            assert(0);
    }
    for(auto i:v1)
    {
        fill(us, us+n+10, 0ll);
        if(dfs1(i.S, i.F, {i.F, i.S})) ans+=mp[{i.F, i.S}];
    }
    for(int it = 1; it <= tim; it++)
    {
        int n;
        for(auto i:d[it])
        {
//            cout<<i.F<<" "<<i.S<<endl;
            g1[i.F].push_back(i.S);
            g_ob1[i.S].push_back(i.F);
            fl[i.F][i.S] = 0;
            fl[i.S][i.F] = 0;
            n = kol[cl[i.F]];
        }
        for(auto i:d[it])
        {
            fl[i.F][i.S] = 2;
            fl[i.S][i.F] = 2;
            int o = 0;
            cnt = 0;
            fill(us, us+n1+10, 0);
            dfs2(i.F);
            if(cnt != n)
                o = 1;
            cnt = 0;
            fill(us, us+n1+10, 0);
            dfs2(i.S);
            if(cnt != n)
                o = 1;
            if(o)
            {
                fl[i.F][i.S] = 1;
                fl[i.S][i.F] = 1;
                ans++;
            }
            else
            {
                fl[i.F][i.S] = 0;
                fl[i.S][i.F] = 0;
            }
        }
        for(auto i:d[it])
        {
            g1[i.F].clear();
            g_ob1[i.S].clear();
            fl[i.F][i.S] = 0;
            fl[i.S][i.F] = 0;
        }
    }
    cout<<ans<<"\n1";
}

