#include<bits/stdc++.h>
#define mp make_pair
using namespace std;
const int N=2e5+5;
int n,w,d,dis[N],vis[N],a[N],ans[N];
vector<int> e[N];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
struct node{
	int l,p,d;
	const bool operator>(const node& x) const{
    	return l>x.l;
  	}	
};
priority_queue<node,vector<node>,greater<node>>f;
void dij(){
	memset(dis,0x3f,sizeof(dis));
	dis[n]=0;
	q.push(mp(0,n));
	while(!q.empty()){
		int u=q.top().second;
		q.pop();
		if(!vis[u]){
			vis[u]=1;
			for(int i=0;i<e[u].size();i++){
				int v=e[u][i];
				if(dis[u]+1<dis[v]){
					dis[v]=dis[u]+1;
					q.push(mp(dis[v],v));
				}
			}
		}
	}
}
int main(){
	freopen("Commute.in","r",stdin);
	freopen("Commute.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>w>>d;
	for(int i(1);i<=w;++i){
		int a,b;
		cin>>a>>b;
		e[b].push_back(a);
	}
	dij();
	for(int i(1);i<=n;++i){
		cin>>a[i];
	}
	for(int i(1);i<=n;++i){
		f.push({i-1+dis[a[i]],a[i],0});
	}
	for(int i(1);i<=d;++i){
		int su,sy;
		cin>>su>>sy;
		f.push({sy+dis[a[su]]-1,a[su],++ans[a[su]]});
		f.push({su+dis[a[sy]]-1,a[sy],++ans[a[sy]]});
		while(f.top().d!=ans[f.top().p]) f.pop();
		cout<<f.top().l<<"\n";
		swap(a[sy],a[su]);
	}
	return 0;
}