#include<bits/stdc++.h>
using namespace std;

const int maxn=55;
const int INF=0x3f3f3f3f;
int n,m,k,mn,mnp,cur,ansp,s,t;
int x[maxn],y[maxn],e[maxn][maxn],banf[maxn],bant[maxn],timf[maxn],timt[maxn];
vector<int>way[maxn];
long long sum,tot,ans;

namespace Flow{
	const int maxv=maxn*2;
	const int maxe=maxn*maxn*2;
	int tot,V;
	int head[maxv],nxt[maxe<<1],to[maxe<<1],cap[maxe<<1],cost[maxe<<1];
	int dist[maxv],prv[maxv];
	bool in[maxv];
	queue<int>que;
	void init(){
		tot=0;
		memset(head,-1,sizeof(head));
	}
	int addedge(int u,int v,int c,int co){
		nxt[tot]=head[u];to[tot]=v;cap[tot]=c;cost[tot]=co;head[u]=tot++;
		nxt[tot]=head[v];to[tot]=u;cap[tot]=0;cost[tot]=-co;head[v]=tot++;
		return tot-1;
	}
	int spfa(int s,int t){
		for(int i=0;i<V;i++)dist[i]=INF,in[i]=false;
		dist[s]=0;
		in[s]=true;
		que.push(s);
		while(!que.empty()){
			int x=que.front();que.pop();
			in[x]=false;
			for(int i=head[x];~i;i=nxt[i])if(cap[i]&&dist[to[i]]>dist[x]+cost[i]){
				dist[to[i]]=dist[x]+cost[i];
				prv[to[i]]=i;
				if(!in[to[i]])
					in[to[i]]=true,que.push(to[i]);
			}
		}
		for(int i=t;i!=s;i=to[prv[i]^1])
			cap[prv[i]]--,cap[prv[i]^1]++;
		return dist[t];
	}
}

int main(){
	scanf("%d%d%d",&n,&m,&k);
	s=2*n;t=2*n+1;
	Flow::V=2*n+2;
	Flow::init();
	for(int i=0;i<n;i++)for(int j=0;j<n;j++)e[i][j]=-1;
	for(int i=0;i<n;i++){
		Flow::addedge(i<<1,i<<1|1,1,-1);
		Flow::addedge(s,i<<1,1,0);
		Flow::addedge(i<<1|1,t,1,0);
	}
	for(int i=0;i<m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		u--;v--;
		e[u][v]=Flow::addedge(u<<1|1,v<<1,1,0);
	}
	for(int i=0;i<k;i++){
		scanf("%d%d",&x[i],&y[i]);
		sum+=x[i];
	}
	ans=sum-x[0];
	ansp=0;
	for(int i=0;i<n;i++)
		banf[i]=bant[i]=-1,timf[i]=timt[i]=k;
	mn=INF;
	mnp=-1;
	for(int i=0;i<k;i++){
		if(y[i]<mn)mn=y[i],mnp=i;
		cur-=Flow::spfa(s,t);
		if(cur==n){
			tot+=mn;
			for(int j=0;j<n;j++){
				if(banf[j]<0){
					int ck=-1;
					for(int k=0;k<n;k++)if(e[k][j]>=0){
						if(Flow::cap[e[k][j]])ck=k;
						Flow::cap[e[k][j]]=Flow::cap[e[k][j]^1]=0;
					}
					if(ck>=0){
						cur-=Flow::spfa(t,j<<1)+Flow::spfa(ck<<1|1,s)+Flow::spfa(s,t);
						if(cur<n){
							banf[j]=mnp;
							timf[j]=i;
							break;
						}
					}
					for(int k=0;k<n;k++)if(e[k][j]>=0&&bant[k]<0)
						Flow::cap[e[k][j]^1]=1;
				}
				if(bant[j]<0){
					int ck=-1;
					for(int k=0;k<n;k++)if(e[j][k]>=0){
						if(Flow::cap[e[j][k]])ck=k;
						Flow::cap[e[j][k]]=Flow::cap[e[j][k]^1]=0;
					}
					if(ck>=0){
						cur-=Flow::spfa(t,ck<<1)+Flow::spfa(j<<1|1,s)+Flow::spfa(s,t);
						if(cur<n){
							bant[j]=mnp;
							timt[j]=i;
							break;
						}
					}
					for(int k=0;k<n;k++)if(e[j][k]>=0&&banf[k]<0)
						Flow::cap[e[j][k]^1]=1;
				}
			}
		}
		assert(cur<n);
		if(sum-x[i+1]-tot>ans)
			ans=sum-x[i+1]-tot,ansp=i+1;
	}
	for(int i=0;i<n;i++){
		way[timf[i]>=ansp?ansp:banf[i]].push_back(-i-1);
		way[timt[i]>=ansp?ansp:bant[i]].push_back(i+1);
	}
	printf("%d\n",2*n+k-int(way[k].size()));
	for(int i=0;i<k;i++){
		for(int j=0;j<int(way[i].size());j++)printf("%d ",way[i][j]);
		printf("0%c",i==k-1?'\n':' ');
	}
	return 0;
}
