[PA2014] Fiolki
题目描述
化学家吉丽想要配置一种神奇的药水来拯救世界。
吉丽有 $n$ 种不同的液体物质,和 $n$ 个药瓶(均从 $1$ 到 $n$ 编号)。初始时,第 $i$ 个瓶内装着 $g_i$ 克的第 $i$ 种物质。
吉丽需要执行一定的步骤来配置药水,第 $i$ 个步骤是将第 $a_i$ 个瓶子内的所有液体倒入第 $b_i$ 个瓶子,此后第 $a_i$ 个瓶子不会再被用到。瓶子的容量可以视作是无限的。
吉丽知道某几对液体物质在一起时会发生反应产生沉淀,具体反应是 $1$ 克 $c_i$ 物质和 $1$ 克 $d_i$ 物质生成 $2$ 克沉淀,一直进行直到某一反应物耗尽。生成的沉淀不会和任何物质反应。
当有多于一对可以发生反应的物质在一起时,吉丽知道它们的反应顺序。每次倾倒完后,吉丽会等到反应结束后再执行下一步骤。
吉丽想知道配置过程中总共产生多少沉淀。
输入输出格式
输入格式
第一行三个整数 $n,m,k$,分别表示药瓶的个数(即物质的种数),操作步数,可以发生的反应数量。
第二行有 $n$ 个整数 $g_1,g_2,…,g_n$,表示初始时每个瓶内物质的质量。
接下来 $m$ 行,每行两个整数 $a_i,b_i$,表示第 $i$ 个步骤。保证 $a_i$ 在以后的步骤中不再出现。
接下来 $k$ 行,每行是一对可以发生反应的物质 $c_i,d_i$,按照反应的优先顺序给出。同一个反应不会重复出现。
输出格式
输出总共产生的沉淀质量。
输入输出样例
输入样例 #1
3 2 1
2 3 4
1 2
3 2
2 3
输出样例 #1
6
说明
对于 $100\%$ 的数据,$0\le m<n\le 2\times 10^5$,$0\le k\le 5\times 10^5$,$1\le g_i\le 10^9$,$1\le a_i,b_i,c_i,d_i\le n$,$a_i\ne b_i$,$c_i\ne d_i$。