You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小星有一棵 n 个节点的有根树，每个节点的编号分别为 1,2,⋯,​n​，并且 1 为树根。刚开始所有点都没有染色，现在给出 ​A​+B 条限制，每条限制又如下两种形式：

A 类限制：x y，表示以 x 为根的子树内（包括节点 ​x​）至少有 y 个点被染色

B 类限制：x y，表示以整棵树中除去以 x 为根的子树的部分，至少有 y 个点被染色

问最少给多少个点染色才能满足所有的限制。如果不存在合法的染色方案，则输出 −1。

输入格式

第一行一个正整数 ​n​，表示树上结点数量。

接下来 ​n​−1 行，每行两个正整数 ​x​,y ，表示 x 与 y 之间有一条边。

接下来 1 行读入整数 ​A​，表示 A 类限制的数量。

接下来 A 行，每行两个整数 ​x​, ​y​，表示一条 A 类限制。

接下来 1 行读入整数 B ，表示 B 类限制的数量。

接下来 B 行，每行两个整数 ​x​, ​y​，表示一条 B 类限制。

输出格式

一行一个整数，表示答案。

样例 #1

样例输入 #1

3
1 2
1 3
2
2 1
3 1
2
2 1
3 1

样例输出 #1

2​

提示

【样例解释】

将 2,3 号点染色就可以满足所有限制。

【数据范围】

对于 30% 的数据，满足 ​n​≤1000。

对于再 30% 的数据，满足 ​B​=0。

对于 100% 的数据，满足 1≤​n​≤100000,0≤​A​,​B​,​x​,​y​≤100000。