题目背景

2025 年 03 月 GESP C++ 八级编程第 2 题

题目描述

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

小杨设置了 $a$ 个好点对 $<u_{1}, v_{1}>$, $<u_{2}, v_{2}>$, $...$, $<u_{a}, v_{a}>$ 和 $1$ 个坏点对 $<b_{u}, b_{v}>$。一个节点能够被删除，当且仅当：

• 删除该节点后对于所有的 $i(1 \leq i \leq a)$，好点对 $u_{i}$ 和 $v_{i}$ 仍然连通；

• 删除该节点后坏点对 $b_{u}$ 和 $b_{v}$ 不连通。

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

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

输入格式

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

之后 $n - 1$ 行，每行包含两个正整数 $x_{i}, y_{i}$，代表存在一条连接节点 $x_{i}$ 和 $y_{i}$ 的边。

之后 $a$ 行，每行包含两个正整数 $u_{i}, v_{i}$，代表一个好点对 $<u_{i}, v_{i}>$。

最后一行包含两个正整数 $b_{u}, b_{v}$，代表坏点对 $<b_{u}, b_{v}>$。

输出格式

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

样例

6 2
1 3
1 5
3 6
3 2
5 4
5 4
5 3
2 6

2

数据范围

对于全部数据，保证有 $1 \leq n \leq 10^6, 0 \leq a \leq 10^5, u_{i} \neq v_{i}, b_{u} \neq b_{v}$。