#include<bits/stdc++.h>
typedef long long LL;
typedef double dl;
#define opt operator
#define pb push_back
#define pii std::pair<LL,LL>
const LL maxn=1e5+9,mod=998244353,inf=0x3f3f3f3f;
LL Read(){
	LL x(0),f(1); char c=getchar();
	while(c<'0' || c>'9'){
		if(c=='-') f=-1; c=getchar();
	}
	while(c>='0' && c<='9'){
		x=(x<<3ll)+(x<<1ll)+c-'0'; c=getchar();
	}return x*f;
}
void Chkmin(LL &x,LL y){
	if(y<x) x=y;
}
void Chkmax(LL &x,LL y){
	if(y>x) x=y;
}
LL add(LL x,LL y){
	return x+=y,x>=mod?x-mod:x;
}
LL dec(LL x,LL y){
	return x-=y,x<0?x+mod:x;
}
LL mul(LL x,LL y){
	return 1ll*x*y%mod;
}
LL Pow(LL base,LL b){
	LL ret(1); while(b){
		if(b&1) ret=mul(ret,base); base=mul(base,base); b>>=1;
	}return ret;
}
namespace Flow{
	struct edge{
		LL to,nxt,f;
	}dis[maxn];
	LL num,n,s,t;
	LL head[maxn],lev[maxn];
	void Add(LL u,LL v,LL f){
		dis[++num]=(edge){v,head[u],f}; head[u]=num;
		dis[++num]=(edge){u,head[v],0}; head[v]=num;
	}
	void Init(LL n0,LL s0,LL t0){
		n=n0; s=s0; t=t0;
		for(LL i=1;i<=n;++i) head[i]=-1;
		num=-1;
	}
	LL Bfs(){
		for(LL i=1;i<=n;++i) lev[i]=0;
		lev[s]=1;
		std::queue<LL> que;
		que.push(s);
		while(que.size()){
			LL u(que.front()); que.pop();
			for(LL i=head[u];i!=-1;i=dis[i].nxt){
				LL v(dis[i].to); if(!dis[i].f || lev[v]) continue;
				lev[v]=lev[u]+1;
				que.push(v);
			}
		}
		return lev[t];
	}
	LL Dfs(LL u,LL f){
		if(u==t) return f;
		LL tmp(f);
		for(LL i=head[u];i!=-1;i=dis[i].nxt){
			LL v(dis[i].to); if(!dis[i].f || lev[v]!=lev[u]+1) continue;
			LL ret(Dfs(v,std::min(dis[i].f,tmp)));
			if(!ret){
				lev[v]=0; continue;
			}
			tmp-=ret;
			dis[i].f-=ret; dis[i^1].f+=ret;
			if(!tmp){
				return f;
			}
		}
		return f-tmp;
	}
	LL Dinic(){
		LL ret(0);
		while(Bfs()){
			ret+=Dfs(s,inf);
		}
		return ret;
	}
}
struct edge{
	LL x,y;
}e[maxn];
LL n,m,K,beg;
LL ers[109],mark[maxn],lim[59];
LL pre[59][59];
pii cost[59];
std::vector<pii> V[59],G[59];
std::vector<LL> S,Ans;
void Init(){
	n=Read(); m=Read(); K=Read();
	for(LL i=1;i<=m;++i){
		LL x(Read()),y(Read());
		e[i]=(edge){x,y};
		V[x].pb(pii(y,i));
		G[y].pb(pii(x,i));
	}
	for(LL i=1;i<=K;++i){
		cost[i].first=Read();
		cost[i].second=Read();
	}
}
LL Get(){
	Flow::Init(2*n+2,2*n+1,2*n+2);
	for(LL i=1;i<=m;++i) if(!mark[i]){
		LL x(e[i].x),y(e[i].y);
		Flow::Add(x,y+n,1);
	}
	for(LL i=1;i<=n;++i){
		Flow::Add(2*n+1,i,1);
	}
	for(LL i=1;i<=n;++i){
		Flow::Add(n+i,2*n+2,1);
	}
	return Flow::Dinic();
}
LL Check(LL x,LL ret){
	if(ers[x]) return 0;
	ers[x]=1;
	for(LL i=1;i<=m;++i) mark[i]=0;
	for(LL u=1;u<=n;++u) if(ers[u]){
		for(LL i=0;i<V[u].size();++i){
			mark[V[u][i].second]=1;
		}
	}
	for(LL u=1;u<=n;++u) if(ers[u+n]){
		for(LL i=0;i<G[u].size();++i){
			mark[G[u][i].second]=1;
		}
	}
	LL tmp(Get());
	//printf("# %lld\n",n-tmp);
	ers[x]=0;
	return (n-tmp)==ret+1;
}
void Fir(){
	LL ret(n-Get());
	//printf("# %lld\n",ret);
	if(ret>K) return;
	for(LL i=K;i>=1;--i){
		lim[i]=i-ret+1;
		Chkmax(lim[i],0);
	}
	LL num(K-ret+1);
	//printf("%lld\n",num);
	for(LL i=1;i<=num;++i){
		LL tmp(0);
		/*
        if(i==1) printf("%lld\n",Check(1,ret)),tmp=1;
		else printf("%lld\n",Check(8,ret+1)),tmp=8;
		*/
		//Check(1,ret);
		//exit(0);
	//	/*
		for(LL j=1;j<=2*n;++j) if(Check(j,ret+i-1)){
			tmp=j; break;
		}
	//	*/
		//printf("(%lld)\n",tmp);
		ers[tmp]=1;
		if(tmp<=n) S.pb(tmp);
		else S.pb(-(tmp-n));
		assert(tmp);
	}
}
void Dfs(LL N,LL M){
	if(!N){
		assert(!M); return;
	}
	Dfs(N-1,M-pre[N][M]);
	LL x(pre[N][M]);
	while(x--){
		Ans.pb(S[beg++]);
	}
	Ans.pb(0);
}
void Solve(){
	Fir();
	static LL f[59][59];
	f[0][0]=0; for(LL i=1;i<=S.size();++i) f[0][i]=-inf;
	for(LL i=1;i<=K;++i){
		for(LL j=0;j<lim[i];++j) f[i][j]=-inf;
		for(LL j=lim[i];j<=S.size();++j){
			LL ret(-inf),ot(0);
			for(LL k=0;k<=j;++k){
				LL tmp=f[i-1][j-k]+std::max(0ll,cost[i].first-k*cost[i].second);
				Chkmax(ret,tmp);
				if(ret==tmp){
					ot=k;
				}
			}
			f[i][j]=ret; pre[i][j]=ot;
		}
	}
	Dfs(K,S.size());
	//printf("#(ans) %lld\n",f[K][S.size()]);
	printf("%d\n",Ans.size());
	for(LL i=0;i<Ans.size();++i){
		printf("%lld ",Ans[i]);
	}puts("");
}
int main(){
	Init();
	Solve();
	return 0;
}



