E. Автобусные маршруты
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Существует страна, состоящая из $$$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$$$) такие, что до города $$$y$$$ из города $$$x$$$ невозможно добраться не более чем двумя автобусными маршрутами.

Вы можете вывести ответ в любом регистре (верхнем или нижнем). Например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительные. ответы.

Пример
Входные данные
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
Выходные данные
YES
NO
1 3
NO
1 2
NO
1 6
Примечание

Ниже приведены иллюстрации к $$$1$$$, $$$2$$$ и $$$4$$$ наборам входных данных: