#include <algorithm>   #include <cassert>   #include <iostream>   #include <queue>   #include <vector>   using namespace std;      typedef long long ll;   typedef pair<int, int> Pii;   typedef vector<Pii> VPii;   typedef vector<int> Vi;   typedef vector<Vi> VVi;   typedef vector<ll> Vll;   typedef vector<Vll> VVll;      const ll INF = 1000000000000000000LL;      Vi toposort(const VVi& g) {       int n = g.size();       Vi deg(n);       for (auto& others : g) {           for (int other : others) {               ++deg[other];           }       }          queue<int> q;       for (int i = 0; i < n; ++i) {           if (deg[i] == 0) {               q.push(i);           }       }          Vi result;       while (!q.empty()) {           int x = q.front();           q.pop();              result.push_back(x);              for (int other : g[x]) {               if (--deg[other] == 0) {                   q.push(other);               }           }       }       return result;   }      Vi findPath(int start, const VVi& rg, Vi& target, const VVi& ban) {       int n = rg.size();       VVi prev(2, Vi(n, -1));       prev[0][start] = start;          queue<Pii> q;       q.push(make_pair(0, start));          int finish = -1;          while (!q.empty()) {           int d = q.front().first;           int x = q.front().second;           q.pop();              if (d == 0) {               if (ban[0][x] == 1) {                   continue;               }               for (int y : rg[x]) {                   if (ban[1][y] == 1) {                       continue;                   }                   if (target[y] != x && prev[1][y] == -1) {                       prev[1][y] = x;                       q.push(make_pair(1, y));                   }               }           } else {               int y = target[x];               if (y == -1) {                   finish = x;                   break;               }                  if (prev[0][y] == -1) {                   prev[0][y] = x;                   q.push(make_pair(0, y));               }           }       }              if (finish == -1) {           return Vi();       }          Vi path;       for (int d = 1, x = finish; x != start; x = prev[d][x], d = 1 - d) {           path.push_back(x);       }       path.push_back(start);       reverse(path.begin(), path.end());       return path;   }      int minSeeds(const VVi& g, const VVi& rg, const VVi& ban) {       int n = g.size();       int seeds = 0;       Vi target(n, -1);       Vi order = toposort(g);       for (int x : order) {           auto path = findPath(x, rg, target, ban);           if (path.empty()) {               ++seeds;           }           assert(path.size() % 2 == 0);           for (int i = 0; i + 1 < path.size(); i += 2) {               int a = path[i];               int b = path[i + 1];               target[b] = a;           }       }       return seeds;   }      Pii nextBan(int currentSeeds, const VVi& g, const VVi& rg, VVi ban) {       int n = g.size();       for (int d = 0; d < 2; ++d) {           for (int x = 0; x < n; ++x) {               if (ban[d][x] == 1) {                   continue;               }               ban[d][x] = 1;               int t = minSeeds(g, rg, ban);               if (t == currentSeeds + 1) {                   return make_pair(d, x);               }               ban[d][x] = 0;           }       }       assert(false);   }      VPii optimalSequence(const VVi& g, const VVi& rg) {       int n = g.size();       VVi ban(2, Vi(n, 0));          int m = minSeeds(g, rg, ban);       VPii result;              for (int i = 0; i < n - m; ++i) {           auto t = nextBan(m + i, g, rg, ban);           result.push_back(t);           ban[t.first][t.second] = 1;       }          return result;   }      Vi optimalPattern(int initial, int n, VPii& cost) {       int k = cost.size();       VVll dp(k + 1, Vll(n + 1));       VVi next(k + 1, Vi(n + 1));       for (int r = k - 1; r >= 0; --r) {           for (int s = initial; s <= n; ++s) {               ll bestScore = 0;               int bestT = -1;               for (int t = max(s, r + 2); t <= n; ++t) {                   int c = t - s;                   ll score = max(0LL, cost[r].first - ll(c) * cost[r].second) + dp[r + 1][t];                   if (bestT == -1 || score > bestScore) {                       bestT = t;                       bestScore = score;                   }               }               dp[r][s] = bestScore;               next[r][s] = bestT;           }       }          Vi pattern;       for (int r = 0, s = initial; r < k; s = next[r][s], ++r) {           pattern.push_back(next[r][s] - s);       }       return pattern;   }      int main() {       int n, m, k;       cin >> n >> m >> k;          VVi g(n), rg(n);       for (int i = 0; i < m; ++i) {           int x, y;           cin >> x >> y;           --x; --y;           g[x].push_back(y);           rg[y].push_back(x);       }          VPii cost(k);       for (int i = 0; i < k; ++i) {           cin >> cost[i].first >> cost[i].second;       }          auto seq = optimalSequence(g, rg);       int initial = n - seq.size();          auto patt = optimalPattern(initial, n, cost);          Vi solution;       int used = 0;       for (int p : patt) {           for (int i = 0; i < p; ++i) {               auto s = seq[used++];               int sign = s.first == 0 ? -1 : 1;               solution.push_back(sign * (s.second + 1));           }           solution.push_back(0);       }          cout << solution.size() << endl;       for (int i = 0; i < solution.size(); ++i) {           if (i != 0) {               cout <<    ;           }           cout << solution[i];       }       cout << endl;   }