Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

F. Stardew Valley
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пеликан-таун представляет из себя $$$n$$$ домов, соединенных $$$m$$$ двунаправленными дорогами. На некоторых дорогах стоят NPC. Фермеру Бубе очень важно пройти по каждой дороге с NPC и поговорить с ними.

Помогите фермеру найти маршрут, для которого выполняются следующие условия:

  • Маршрут начинается у некоторого дома, проходит по некоторым дорогам, и заканчивается в том же доме.
  • Маршрут не проходит ни по какой дороге более одного раза (в обоих направлениях вместе).
  • Маршрут проходит по каждой дороге с 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» будут распознаны как положительный ответ).

Пример
Входные данные
3
3 2
1 2 1
2 3 1
3 3
1 2 1
1 3 1
2 3 0
5 9
1 2 0
5 2 1
5 4 1
5 1 1
2 3 1
5 2 1
4 1 0
4 3 0
5 2 0
Выходные данные
NO
YES
3
1 2 3 1 
YES
7
1 2 5 4 3 2 5 1
Примечание

Обратите внимание, что в третьем наборе входных данных присутствуют кратные ребра $$$(5, 2)$$$. Вам обязательно нужно пройти по двум из них.