← 返回题目列表

Codeforces · 1827/E

E. 巴士路线

中文机器翻译题面 查看原题

有一个国家由 $$$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$$$ 最多不可能使用两条公交路线到达城市 $$$y$$$。

您可以在任何情况下输出答案(大写或小写)。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。

示例

输入 #1

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

输出 #1

YES
NO
1 3
NO
1 2
NO
1 6

注意

以下是测试用例 $$$1$$$、$$$2$$$ 和 $$$4$$$ 的图表:

样本 1

样本 2

示例 4