5731 - GESP:2025-3月等级8-T2-割裂
时间限制 : 2 秒
内存限制 : 128 MB
小杨有一棵包含 n个节点的树,其中节点的编号从1到n。 小杨设置了a个好点对< u1,v1 >,< u2,v2 >,...< ua,va > 和1个坏点对< bu,bv >。一个节点能够被删除,
当且仅当:
.删除该节点后对于所有的i(1<=i<=a),好点对ui和vi仍然连通;
.删除该节点后坏点对bu和bi不连通。
如果点对中的任意一个节点被删除,其视为不连通。 小杨想知道,有多少个节点能够被删除。
输入
第一行包含两个正整数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