E. Cycling City
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы организуете велосипедную гонку на улицах города. В городе присутствует n перекрестков, некоторые пары из которых соединены дорогами; по каждой из дорог можно перемещаться в любую сторону. Никакие две дороги не соединяют одну и ту же пару перекрестков, и никакая дорога не соединяет перекресток с самим собой.

Вы хотите, чтобы в гонке могли принять участие как профессиональные спортсмены, так и начинающие велосипедисты, и для этого вы проведете гонку в трех номинациях: легкая, средняя и сложная; каждый участник выберет себе сложность по силам. Для каждой номинации необходимо выбрать свой маршрут — цепочку перекрестков, последовательно соединенных дорогами. Маршруты должны удовлетворять следующим условиям:

  • все три маршрута должны стартовать на одном и том же перекрестке, а также финишировать на одном и том же перекрестке (места старта и финиша не могут совпадать);
  • во избежание столкновений никакие два маршрута не могут иметь общих перекрестков (за исключением общих старта и финиша), а также не могут проходить по одной и той же дороге (независимо от направления прохождения по этой дороге);
  • ни один маршрут не должен дважды проходить через один и тот же перекресток либо дважды проходить по одной и той же дороге (независимо от направления прохождения по этой дороге).

Подготовка к соревнованиям скоро начнется, и вам нужно как можно быстрее определиться с маршрутами гонки. Длина маршрутов не играет роли, важно лишь, чтобы все перечисленные требования были удовлетворены.

Входные данные

В первой строке записано два целых числа n и m (1 ≤ n, m ≤ 2·105) — количество перекрестков и дорог соответственно.

В следующих m строках через пробел записано по два целых числа — номера перекрестков, соединенных очередной дорогой (перекрестки нумеруются, начиная с 1). Гарантируется, что каждая пара перекрестков соединена не более, чем одной дорогой, и никакая дорога не соединяет перекресток сам с собой.

Обратите внимание, что возможность добраться от любого перекрестка до любого другого по дорогам не гарантируется.

Выходные данные

Если проложить маршруты возможно, в первой строке выведите «YES». В следующих трех строках выведите описания каждого из трёх маршрутов в формате «l p1 ... pl», гле l — количество перекрёстков в маршруте, а p1, ..., pl — их номера в порядке следования. Маршруты должны удовлетворять всем приведенным в условии требованиям.

Если же проложить маршруты в соответствии с указанными требованиями невозможно, выведите NO.

Примеры
Входные данные
4 4
1 2
2 3
3 4
4 1
Выходные данные
NO
Входные данные
5 6
1 2
1 3
1 4
2 5
3 5
4 5
Выходные данные
YES
3 5 4 1
3 5 3 1
3 5 2 1