#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cassert>
using namespace std;
int n,m,k,vx[100],vy[100];long long sum[100];bool mp[100][100],used[100],tmp[100],clsa[100],clsb[100];int match[100];vector<pair<int,int> >ansseq,curseq;
bool dfs(int v){for(int i=1;i<=n;++i)if(mp[v][i]&&!used[i]){used[i]=1;if(!match[i]||dfs(match[i])){match[i]=v;	return 1;}}return 0;}
int maxmatch(){int cnt=0;	for(int i=1;i<=n;++i){memset(used+1,0,n);cnt+=dfs(i);}memset(match+1,0,n<<2);return cnt;}
int main(){scanf("%d %d %d",&n,&m,&k);for(int i=1,x,y;i<=m;++i){scanf("%d %d",&x,&y);mp[x][y]=1;}for(int i=1;i<=k;++i)scanf("%d %d",&vx[i],&vy[i]),sum[i]=sum[i-1]+vx[i];
	int cnt=maxmatch();int mi=0x3f3f3f3f,mip=0;long long ans=-1,cur=0;for(int i=1;i<=k;++i){if(vy[i]<mi)mi=vy[i],mip=i;if(cur+sum[k]-sum[i]>ans)
		{ans=cur+sum[k]-sum[i];ansseq=curseq;for(int j=1;j<=n;++j)if(!clsa[j])ansseq.emplace_back(make_pair(i,j));
			for(int j=1;j<=n;++j)if(!clsb[j])ansseq.emplace_back(make_pair(i,-j));}	cur+=vx[i];
		if(i+cnt==n){cur-=mi;bool flag=0;for(int j=1;j<=n;++j){	if(clsa[j])continue;for(int k=1;k<=n;++k)tmp[k]=mp[j][k],mp[j][k]=0;
				if(maxmatch()<cnt){	curseq.emplace_back(make_pair(mip,j));flag=1;clsa[j]=1;	break;}else for(int k=1;k<=n;++k)mp[j][k]=tmp[k];}
			for(int j=1;j<=n&&!flag;++j){if(clsb[j])continue;for(int k=1;k<=n;++k)tmp[k]=mp[k][j],mp[k][j]=0;
				if(maxmatch()<cnt){	curseq.emplace_back(make_pair(mip,-j));	flag=1;clsb[j]=1;break;	}else for(int k=1;k<=n;++k)mp[k][j]=tmp[k];}
			assert(flag);--cnt;}}if(cur>ans)ans=cur,ansseq=curseq;printf("%d\n",(int)ansseq.size()+k);int t=0;
	for(int i=1;i<=k;++i){while(t<(int)ansseq.size()&&ansseq[t].first==i)printf("%d ",ansseq[t].second),++t;printf("0 ");}return 0;}