package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n, m, k int
	if _, err := fmt.Fscan(in, &n, &m, &k); err != nil {
		return
	}

	adj := make([][]int, n)
	for i := 0; i < m; i++ {
		var u, v int
		fmt.Fscan(in, &u, &v)
		u--
		v--
		adj[u] = append(adj[u], v)
	}

	x := make([]int64, k+1)
	y := make([]int64, k+1)
	for i := 1; i <= k; i++ {
		fmt.Fscan(in, &x[i], &y[i])
	}

	
	matchR := make([]int, n) 
	for i := range matchR {
		matchR[i] = -1
	}
	matchL := make([]int, n) 
	for i := range matchL {
		matchL[i] = -1
	}

	var dfs func(u int, visR []bool) bool
	dfs = func(u int, visR []bool) bool {
		for _, v := range adj[u] {
			if visR[v] {
				continue
			}
			visR[v] = true
			if matchR[v] == -1 || dfs(matchR[v], visR) {
				matchR[v] = u
				matchL[u] = v
				return true
			}
		}
		return false
	}

	M0 := 0
	for u := 0; u < n; u++ {
		visR := make([]bool, n)
		if dfs(u, visR) {
			M0++
		}
	}

	
	visL := make([]bool, n)
	visR := make([]bool, n)

	var dfsAlt func(u int)
	dfsAlt = func(u int) {
		visL[u] = true
		for _, v := range adj[u] {
			if visR[v] {
				continue
			}
			if matchL[u] != v { 
				visR[v] = true
				if matchR[v] != -1 && !visL[matchR[v]] {
					dfsAlt(matchR[v])
				}
			}
		}
	}

	for u := 0; u < n; u++ {
		if matchL[u] == -1 {
			dfsAlt(u)
		}
	}

	
	Lcover := make([]bool, n)
	Rcover := make([]bool, n)
	for u := 0; u < n; u++ {
		if !visL[u] {
			Lcover[u] = true
		}
	}
	for v := 0; v < n; v++ {
		if visR[v] {
			Rcover[v] = true
		}
	}

	
	acts := make([]int, 0, M0)
	for u := 0; u < n; u++ {
		if Lcover[u] {
			acts = append(acts, u+1) 
		}
	}
	for v := 0; v < n; v++ {
		if Rcover[v] {
			acts = append(acts, -(v + 1)) 
		}
	}

	P0 := n - M0
	rawNeed := func(i int) int {
		val := i - P0 + 1
		if val < 0 {
			return 0
		}
		return val
	}
	R := rawNeed(k)
	if R < 0 {
		R = 0
	}
	if R > M0 {
		R = M0
	}

	need := make([]int, k+1)
	for i := 1; i <= k; i++ {
		ni := rawNeed(i)
		if ni > R {
			ni = R
		}
		need[i] = ni
	}

	
	const INF int64 = 1<<62 - 1
	dp := make([][]int64, k+1)
	par := make([][]int, k+1)
	for i := 0; i <= k; i++ {
		dp[i] = make([]int64, R+1)
		par[i] = make([]int, R+1)
		for a := 0; a <= R; a++ {
			dp[i][a] = INF
			par[i][a] = -1
		}
	}
	dp[0][0] = 0

	for i := 1; i <= k; i++ {
		for aPrev := 0; aPrev <= R; aPrev++ {
			if dp[i-1][aPrev] == INF {
				continue
			}
			maxT := R - aPrev
			for t := 0; t <= maxT; t++ {
				aNew := aPrev + t
				if aNew < need[i] {
					continue
				}
				costAdd := y[i] * int64(t)
				if costAdd > x[i] {
					costAdd = x[i]
				}
				nv := dp[i-1][aPrev] + costAdd
				if nv < dp[i][aNew] {
					dp[i][aNew] = nv
					par[i][aNew] = aPrev
				}
			}
		}
	}

	
	tassign := make([]int, k+1)
	curA := R
	for i := k; i >= 1; i-- {
		prevA := par[i][curA]
		if prevA < 0 {
			prevA = 0
		}
		tassign[i] = curA - prevA
		curA = prevA
	}

	
	totalOps := R + k
	res := make([]int, 0, totalOps)
	p := 0
	for i := 1; i <= k; i++ {
		for s := 0; s < tassign[i]; s++ {
			res = append(res, acts[p])
			p++
		}
		res = append(res, 0)
	}

	fmt.Fprintln(out, totalOps)
	for i := 0; i < totalOps; i++ {
		if i > 0 {
			fmt.Fprint(out, " ")
		}
		fmt.Fprint(out, res[i])
	}
	fmt.Fprintln(out)
}