该国有 $$$n$$$ 个城市。
两名候选人正在争夺总统职位。选举已定在未来,两位候选人都已经计划好了如何将城市与道路连接起来。这两个计划都将仅使用 $$$n - 1$$$ 道路连接所有城市。也就是说,每个计划都可以被视为一棵树。两位候选人还指定了他们在 $$$n$$$ 城市中选择的首都(第一位候选人为 $$$x$$$,第二位候选人为 $$$y$$$),这可能相同也可能不同。
每个城市都有建设港口的潜力(一个城市最多可以有一个港口)。在第 $$$i$$$ 个城市建造港口会带来 $$$a_i$$$ 金额。然而,每个候选人都有他的具体要求。要求的形式如下:
- $$$k$$$ $$$x$$$,这意味着候选人想要在其树的第 $$$k$$$ 城市的子树中精确构建 $$$x$$$ 端口(该树以他选择的首都为根)。
找出在满足两个候选人的所有要求的情况下可以获得的最大收入,如果不可能,则打印 -1。
另外保证每位候选人都指定了他选择的首都的港口需求。
输入
第一行包含整数 $$$n$$$、$$$x$$$ 和 $$$y$$$ ($$$1 \le n \le 500$$$, $$$1 \le x, y \le n$$$) — 分别是城市数量、第一个候选者的首都和第二个候选者的首都。
下一行包含整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 100\,000$$$) - 如果在相应城市建造港口所获得的收入。
接下来的 $$$n - 1$$$ 行包含整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$),表示第一个候选树中城市之间的边。
接下来的 $$$n - 1$$$ 行中的每一行都包含整数 $$$u'_i$$$ 和 $$$v'_i$$$ ($$$1 \le u'_i, v'_i \le n$$$, $$$u'_i \ne v'_i$$$),表示第二个候选树中城市之间的边。
下一行包含一个整数$$$q_1$$$ ($$$1 \le q_1 \le n$$$),表示第一个候选人的需求数量。
接下来的 $$$q_1$$$ 行包含两个整数 $$$k$$$ 和 $$$x$$$ ($$$1 \le k \le n$$$, $$$1 \le x \le n$$$) - 其子树中的城市编号和端口数量。
下一行包含一个整数$$$q_2$$$ ($$$1 \le q_2 \le n$$$),表示第二个候选人的需求数量。
接下来的 $$$q_2$$$ 行包含两个整数 $$$k$$$ 和 $$$x$$$ ($$$1 \le k \le n$$$, $$$1 \le x \le n$$$) - 城市编号和其子树中的端口数量。
可以保证,给定的边对应于有效的树,每个候选者最多给出一次关于每个城市的需求,并且每个候选者都指定了他选择的首都的端口需求。也就是说,城市$$$x$$$总是在第一个候选者的要求中给出,而城市$$$y$$$总是在第二个候选者的要求中给出。
输出
精确打印一个整数 - 在满足两位候选人的要求的同时可以获得的最大可能收入,如果无法满足所有要求,则为 -1。
示例
输入 #1
4 1 2 1 2 3 4 1 2 1 3 3 4 1 2 2 3 1 4 2 1 3 4 1 1 2 3
输出 #1
9
输入 #2
5 1 1 3 99 99 100 2 1 2 1 3 3 4 3 5 1 3 1 2 2 4 2 5 2 1 2 3 1 2 1 2 2 1
输出 #2
198
输入 #3
4 1 2 1 2 3 4 1 2 1 3 3 4 2 1 2 4 4 3 1 1 4 2 4 1 2 4
输出 #3
-1
注意
在第一个示例中,最佳方案是在 $$$2$$$、$$$3$$$ 和 $$$4$$$ 城市建设港口,这满足了两个候选人的所有需求,并提供等于 $$$2 + 3 + 4 = 9$$$ 的收入。
在第二个示例中,最佳方案是在 $$$2$$$ 和 $$$3$$$ 城市建设港口,这满足了两个候选人的所有需求,并提供等于 $$$99 + 99 = 198$$$ 的收入。
在第三个示例中,不可能以指定两个候选者的所有需求的方式构建端口,因此答案为-1。