有一个国家由 $$$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