Существует страна, состоящая из \(n\) городов и соединяющих их \(n - 1\) двунаправленных дорог, так что мы можем путешествовать между любыми двумя городами по этим дорогам. Другими словами, эти города и дороги образуют дерево.
Есть \(m\) автобусных маршрутов, соединяющих города между собой. Автобусный маршрут между городами \(x\) и \(y\) позволяет вам путешествовать между любыми двумя городами по простому пути между \(x\) и \(y\) по этому маршруту.
Определите, можно ли из каждой пары городов \(u\) и \(v\) проехать из \(u\) в \(v\), используя не более двух автобусных маршрутов.
Выходные данные
Для каждого теста выведите «YES», если вы можете путешествовать между любой парой городов, используя не более двух автобусных маршрутов.
В противном случае выведите «NO». В следующей строке выведите два города \(x\) и \(y\) (\(1 \le x, y \le n\)) такие, что до города \(y\) из города \(x\) невозможно добраться не более чем двумя автобусными маршрутами.
Вы можете вывести ответ в любом регистре (верхнем или нижнем). Например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительные. ответы.
Примечание
Ниже приведены иллюстрации к \(1\), \(2\) и \(4\) наборам входных данных:
Примеры
| № | Входные данные | Выходные данные |
|
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
|
YES
NO
1 3
NO
1 2
NO
1 6
|