#include <bits/stdc++.h>

using namespace std;

int n, m, k;
vector<vector<int>> adj;
vector<int> match_R, match_L;
vector<bool> visited;

int augment(int l){
  if(visited[l]) return 0;
  visited[l] = true;

  for(int r: adj[l]){
    if(match_R[r] == -1 or augment(match_R[r])){
      match_L[l] = r;
      match_R[r] = l;
      return 1;
    }
  }

  return 0;
}

int mcbm(){
  match_R.assign(n+1, -1);
  match_L.assign(n+1, -1);
  int matches = 0;

  for(int l = 1; l <= n; l++){
    visited.assign(n+1, false);
    matches += augment(l);
  }

  return matches;
}

vector<int> mvc_vertices;
vector<bool> Z;

void dfs_konig(int l){
  if(Z[l]) return;
  Z[l] = true;

  for(int r: adj[l]){
    if(match_L[l] == r) continue;
    Z[r + n] = true;

    if(match_R[r] != -1){
      dfs_konig(match_R[r]);
    }
  }
}

void find_mvc(){
  Z.assign(2*n+1, false);

  for(int l = 1; l <= n; l++){
    if(match_L[l] == -1){
      dfs_konig(l);
    }
  }

  mvc_vertices.clear();

  for(int u = 1; u <= n; u++){
    if(!Z[u]) mvc_vertices.push_back(u);
    if(Z[u + n]) mvc_vertices.push_back(-u);
  }
}

vector<int> x, y;
vector<vector<long long>> memo;

long long max_points(int i, int mpc){
  if(i > k) return 0;

  long long &ret = memo[i][mpc];
  if(ret != -1) return ret;

  if(mpc > k){
    return ret = x[i] + max_points(i+1, mpc);
  }

  int pts = x[i];
  for(int n_mpc = mpc; n_mpc <= k+1; n_mpc++){
    if(n_mpc > i){
      ret = max(ret, pts + max_points(i+1, n_mpc));
    }
    pts = max(0, pts - y[i]);
  }

  return ret;
}

vector<int> ops;

void find_ops(int i, int mpc){
  if(i > k) return;

  if(mpc > k){
    ops.push_back(0);
    find_ops(i+1, mpc);
    return;
  }

  int pts = x[i];
  for(int n_mpc = mpc; n_mpc <= k+1; n_mpc++){
    if(n_mpc > i){
      if(max_points(i, mpc) == pts + max_points(i+1, n_mpc)){
	ops.push_back(0);
	find_ops(i+1, n_mpc);
	break;
      }
    }
    pts = max(0, pts - y[i]);
    ops.push_back(mvc_vertices.back());
    mvc_vertices.pop_back();
  }
}

int main(){
  while(scanf("%d%d%d", &n, &m, &k) > 0){
    adj.assign(n+1, vector<int>());

    for(int i = 0; i < m; i++){
      int u, v;
      scanf("%d%d", &u, &v);
      adj[u].push_back(v);
    }

    int mpc = n - mcbm();
    find_mvc();

    x.resize(k+1);
    y.resize(k+1);
    for(int i = 1; i <= k; i++){
      scanf("%d%d", &x[i], &y[i]);
    }

    memo.assign(k+1, vector<long long>(k+2, -1));
    // printf("%d\n", max_points(1, mpc));

    ops.clear();
    find_ops(1, mpc);

    printf("%d\n", (int)ops.size());

    for(int i = 0; i < ops.size(); i++){
      printf("%d%c", ops[i], i+1 == ops.size() ? '\n' : ' ');
    }

    exit(0);
  }
}
