#include <fstream>
#include <vector>
#include <deque>
#include <cstring>
#include <queue>
#define NMAX 10005
#define pb push_back
#define INF 1e9
using namespace std;

ifstream f("cuplaj.in");
ofstream g("cuplaj.out");

int flow_cap[NMAX][NMAX];
vector<int> G[NMAX];
int n, m, e;
bool visited[NMAX];
int parent[NMAX];

void read_data(){
    f >> n >> m >> e;
    for(int i = 0; i<=e; i++){
        int x, y;
        f >> x >> y;
        G[x].pb(y);
        G[y].pb(x);
        G[0].pb(x);
        G[x].pb(0);
        G[e + 1].pb(y);
        G[y].pb(e + 1);
        flow_cap[x][y] += 1;
        flow_cap[0][x] += 1;
        flow_cap[y][e + 1] += 1;
    }
}

bool bfs(int source, int dest){
    memset(visited, false, sizeof(visited));
    memset(parent, 0, sizeof(parent));
    visited[source] = true;
    parent[source] = -1;
    queue<int> q;
    q.push(source);
    while(!q.empty()){
        int node = q.front();
        q.pop();
        if(node == dest){
            continue;
        }
        for(const auto& adj : G[node]){
            if(!visited[adj] && flow_cap[node][adj] > 0){
                q.push(adj);
                visited[adj] = true;
                parent[adj] = node;
            }
        }
    }
    return visited[dest];
}

int get_flow(int source, int dest){
    int max_flow = 0, min_cap;
    while(bfs(source, dest)){
        for(const auto& curr_node : G[dest]){
            if(!visited[curr_node] || flow_cap[curr_node][dest] <= 0){
                continue;
            }
            min_cap = INF;
            parent[dest] = curr_node;
            for(int i = dest; i != source; i = parent[i]){
                min_cap = min(min_cap, flow_cap[parent[i]][i]);
            }

            for(int i = dest; i != source; i = parent[i]){
                flow_cap[parent[i]][i] -= min_cap;
                flow_cap[i][parent[i]] += min_cap;
            }
        }
        max_flow ++;
    }
    return max_flow;
}

int main(){
    read_data();
    g << get_flow(0, e + 1) + 1;
    return 0;
}