Пеликан-таун представляет из себя \(n\) домов, соединенных \(m\) двунаправленными дорогами. На некоторых дорогах стоят NPC. Фермеру Бубе очень важно пройти по каждой дороге с NPC и поговорить с ними.
Помогите фермеру найти маршрут, для которого выполняются следующие условия:
- Маршрут начинается у некоторого дома, проходит по некоторым дорогам, и заканчивается в том же доме.
- Маршрут не проходит ни по какой дороге более одного раза (в обоих направлениях вместе).
- Маршрут проходит по каждой дороге с NPC ровно один раз.
Обратите внимание, фермер может ходить по дорогам без NPC, также, вам
не нужно минимизировать длину маршрута.
Гарантируется, что если в Пеликан-тауне оставить только дороги с NPC, то можно будет добраться от любого дома до любого другого.
Выходные данные
Для каждого набора входных данных, если решения не существует, то выведите «No» (без кавычек).
Иначе выведите «Yes» (без кавычек), после этого выведите \(k\) — количество дорог в маршруте. В следующей строке выведите \(k + 1\) число — дома маршрута в порядке обхода. Обратите внимание, что первый дом должен совпадать с последним, поскольку маршрут циклический.
Если существуют несколько решений, вы можете вывести любое из них.
Вы можете вывести каждую букву в любом регистре (например, «YES», «Yes», «yes», «yEs» будут распознаны как положительный ответ).
Примечание
Обратите внимание, что в третьем наборе входных данных присутствуют кратные ребра \((5, 2)\). Вам обязательно нужно пройти по двум из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|