Пеликан-таун представляет из себя $$$n$$$ домов, соединенных $$$m$$$ двунаправленными дорогами. На некоторых дорогах стоят NPC. Фермеру Бубе очень важно пройти по каждой дороге с NPC и поговорить с ними.
Помогите фермеру найти маршрут, для которого выполняются следующие условия:
Гарантируется, что если в Пеликан-тауне оставить только дороги с NPC, то можно будет добраться от любого дома до любого другого.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
В первой строке каждого набора входных данных даны два целых числа $$$n$$$ и $$$m$$$ ($$$2 \leq n \leq 5 \cdot 10^5, 1 \leq m \leq 5 \cdot 10^5$$$) — количество домов и дорог в Pelican town соответственно.
В каждой из следующих $$$m$$$ строк даны три целых числа $$$u$$$, $$$v$$$ и $$$c$$$ ($$$1 \leq u, v \leq n, c = 0/1$$$) — концы дороги и находятся ли NPC на этой дороге. Если $$$c = 1$$$, то на дороге стоят NPC. Если $$$c = 0$$$, то на дороге нет NPC.
В графе могут быть кратные ребра и петли, причем, если есть кратные ребра, на которых стоят NPC, то маршрут должен проходить по всем таким дорогам.
Гарантируется, что если в Пеликан-тауне оставить только дороги с NPC, то можно будет добраться от любого дома до любого другого.
Гарантируется, что сумма $$$n$$$ и $$$m$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^5$$$.
Для каждого набора входных данных, если решения не существует, то выведите «No» (без кавычек).
Иначе выведите «Yes» (без кавычек), после этого выведите $$$k$$$ — количество дорог в маршруте. В следующей строке выведите $$$k + 1$$$ число — дома маршрута в порядке обхода. Обратите внимание, что первый дом должен совпадать с последним, поскольку маршрут циклический.
Если существуют несколько решений, вы можете вывести любое из них.
Вы можете вывести каждую букву в любом регистре (например, «YES», «Yes», «yes», «yEs» будут распознаны как положительный ответ).
33 21 2 12 3 13 31 2 11 3 12 3 05 91 2 05 2 15 4 15 1 12 3 15 2 14 1 04 3 05 2 0
NO YES 3 1 2 3 1 YES 7 1 2 5 4 3 2 5 1
Обратите внимание, что в третьем наборе входных данных присутствуют кратные ребра $$$(5, 2)$$$. Вам обязательно нужно пройти по двум из них.
Название |
---|