CF1827E Bus Routes

有一个国家包含 $n$ 个城市和 $n-1$ 条双向道路连接这些城市，使得你可以通过这些道路在任意两个城市之间旅行。换句话说，这些城市和道路构成了一棵树。 有 $m$ 条公交线路连接这些城市。每一条连接城市 $x$ 和城市 $y$ 的公交线路，允许你通过这条线路在 $x$ 和 $y$ 之间的简单路径上的任意两个城市之间旅行。 请判断，对于任意一对城市 $u$ 和 $v$，你是否可以使用至多两条公交线路从 $u$ 到达 $v$。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 5 \cdot 10^5, 0 \le m \le 5 \cdot 10^5$），分别表示城市数量和公交线路数量。 接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$，表示有一条道路连接城市 $u$ 和城市 $v$（$1 \le u, v \le n, u \neq v$）。保证这些城市和道路构成一棵树。 接下来的 $m$ 行，每行包含两个整数 $x$ 和 $y$，表示有一条公交线路连接城市 $x$ 和城市 $y$（$1 \le x, y \le n$）。 保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$，$m$ 的总和不超过 $5 \cdot 10^5$。

对于每个测试用例，如果你可以在任意一对城市之间使用至多两条公交线路到达，输出 "YES"。 否则，输出 "NO"。在下一行输出两个城市 $x$ 和 $y$（$1 \le x, y \le n$），使得无法在至多两条公交线路内从 $x$ 到达 $y$。 你可以以任意大小写输出答案。例如，"yEs"、"yes"、"Yes" 和 "YES" 都会被识别为肯定的回答。

以下是第 $1$、$2$、$4$ 个测试用例的图示：  样例 1  样例 2  样例 4 由 ChatGPT 4.1 翻译