A67569 | 割裂

3.2 编程题 2

试题名称：割裂

时间限制：4.0 s

内存限制：512.0 MB

3.2.8 题面描述

小杨有一棵包含n个节点的树，其中节点的编号从1到n。

小杨设置了a个好点对｛＜u₁,u₁＞,＜u₂,u₂＞,…,＜u_a,u_a＞｝和1个坏点对＜b_u,b_u。一个节点能够被删除，当且仅当：

删除该节点后对于所有的i(1≤i≤a)，好点对u_i和u_i仍然连通；

删除该节点后坏点对b_u和b_u不连通。

如果点对中的任意一个节点被删除，其视为不连通。

小杨想知道，有多少个节点能够被删除。

3.2.9 输入格式

第一行包含两个正整数n,a，含义如题面所示。

之后n-1行，每行包含两个正整数x_i,y_i，代表存在一条连接节点x_i和y_i的边。

之后a行，每行包含两个正整数u_i,u_i，代表一个好点对＜u_i,u_i＞。

最后一行包含两个正整数b_u,b_u，代表坏点对＜b_u,b_u＞。

3.2.10 输出格式

输出一个正整数，代表能够删除的节点个数。

3.2.11 样例

3.2.12 输入样例

3.2.13 输出样例

3.2.14 数据范围

对于全部数据，保证有1≤n≤10⁶,0≤a≤10⁵,u_i≠u_i,b_u≠b_u。