⼩杨有一棵包含 n 个节点的树 ,其中节点的编号从 1 到 n 。 ⼩杨设置了 a 个好点对{< u1,v1 > , < U2 , v2 >,…, < ua , va >}和 1 个坏点对 < bu , bv, > 。一个节点能够被删除 ,当 且仅当: 删除该节点后对于所有的 i(1 ≤ i ≤ a) ,好点对 ui 和 vi 仍然连通; 删除该节点后坏点对bu 和 bv, 不连通。 如果点对中的任意一个节点被删除 ,其视为不连通。 ⼩杨想知道 ,有多少个节点能够被删除。
第一⾏包含两个正整数 n, a ,含义如题⾯所⽰ 。 之后 n -1 ⾏ ,每⾏包含两个正整数 xi , yi ,代表存在一条连接节点 xi 和 yi 的边。 之后 a ⾏ ,每⾏包含两个正整数 ui, vi ,代表一个好点对 < ui, vi > 。 最后一⾏包含两个正整数bu , bv, ,代表坏点对 < bu , bv, > 。
输出一个正整数 ,代表能够删除的节点个数。
6 2 1 3 1 5 3 6 3 2 5 4 5 4 5 3 2 6
2
数据范围
对于全部数据 ,保证有 1 ≤ n ≤ 10^6 , 0 ≤ a ≤ 10^5 , ui≠vi , bu≠bv,