#include<bits/stdc++.h>
using namespace std;
const int N=2e4+5;
int fa[N];
int sz[N];
int a[N];
bool dp[N];
int get(int x){
    if(fa[x]==x) return x;
    return fa[x]=get(fa[x]);
}
int main(){
	int n,m,k;cin>>n>>m>>k;
    for(int i=1;i<=n;i++) fa[i]=i,sz[i]=1;
    for(int i=1;i<=k;i++) {
		int x,y;cin>>x>>y;
        int gx=get(x),gy=get(y);
        if(gx!=gy){
    		fa[gx]=gy;
            sz[gy]+=sz[gx];
        }
	}
    int tot=0;
    for(int i=1;i<=n;i++){
        if(fa[i]==i){
            a[++tot]=sz[i];
            //cout<<"我们放进去了一个有"<<sz[i]<<"大小的商品"<<endl;
        }
    }
    //cout<<a[1]<<" "<<a[2]<<endl;
    dp[0]=1;
    for(int i=1;i<=tot;i++){
        for(int j=a[i];j<=n;j++){
            if(dp[j-a[i]]){
                dp[j]=1;
                //cout<<"我们通过"<<j-a[i]<<"更新了"<<j<<endl;
            }
        }
    }
    int minn=2147483647;
    int idx;
    for(int i=1;i<=n;i++) 
        if(dp[i]){
            //cout<<i<<"是可实现的"<<endl;
            if(abs(m-i)<minn) minn=abs(m-i),idx=i;
        }
   	cout<<idx;
	return 0;
}