#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;
}