CF1827E.Bus Routes

There is a country consisting of $n$ cities and $n - 1$ bidirectional roads connecting them such that we can travel between any two cities using these roads. In other words, these cities and roads form a tree.

There are $m$ bus routes connecting the cities together. A bus route between city $x$ and city $y$ allows you to travel between any two cities in the simple path between $x$ and $y$ with this route.

Determine if for every pair of cities $u$ and $v$, you can travel from $u$ to $v$ using at most two bus routes.

有一个由 $n$ 座城市和 $n - 1$ 条双向道路组成的国家，这些道路连接所有城市，使得任意两座城市之间均可通过道路互相到达。换言之，这些城市与道路构成一棵树。

共有 $m$ 条公交线路连接这些城市。一条从城市 $x$ 到城市 $y$ 的公交线路，允许你仅使用该线路在 $x$ 与 $y$ 之间的简单路径上的任意两座城市间通行。

请判断：对于每一对城市 $u$ 和 $v$，是否均能至多使用两条公交线路从 $u$ 到达 $v$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($2 \le n \le 5 \cdot 10^5, 0 \le m \le 5 \cdot 10^5$) — the number of cities and the number of bus routes.

Then $n - 1$ lines follow. Each line contains two integers $u$ and $v$ denoting a road connecting city $u$ and city $v$ ($1 \le u, v \le n, u \neq v$). It is guaranteed that these cities and roads form a tree.

Then $m$ lines follow. Each line contains two integers $x$ and $y$ denoting a bus route between city $x$ and city $y$ ($1 \le x, y \le n$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$ and the sum of $m$ over all test cases does not exceed $5 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, output "YES" if you can travel between any pair of cities using at most two bus routes.

Otherwise, output "NO". In the next line, output two cities $x$ and $y$ ($1 \le x, y \le n$) such that it is impossible to reach city $y$ from city $x$ using at most two bus routes.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

对于每个测试用例，如果可以通过至多两条公交线路在任意两个城市之间通行，则输出 "YES"。

否则，输出 "NO"。在下一行输出两个城市 $x$ 和 $y$（$1 \le x, y \le n$），使得无法通过至多两条公交线路从城市 $x$ 到达城市 $y$。

你可以以任意大小写形式输出答案（大写或小写均可）。例如，字符串 "yEs"、"yes"、"Yes" 和 "YES" 均会被识别为肯定回答。

Here are the graphs of test case $1$, $2$, and $4$:

Sample 1

Sample 2

Sample 4

以下是测试用例 $1$、$2$ 和 $4$ 的图示：

样例 1

样例 2

样例 4