Рабочее место участника

Однажды утром Трурль повесил на дверь записку "Ушел к Клапауцию" и отправился в гости. Подойдя к дому Клапауция, он увидел, что дверь заперта, а на двери висит записка "Пошел в гости к Трурлю". "Как это я не заметил его по дороге?" – подумал Трурль, сделал приписку на записке и отправился обратно. В пути он внимательно смотрел по сторонам, но Клапауция так и не встретил. На своей двери Трурль обнаружил записку с припиской "Не застал. Иду домой. Клапауций".

Это вполне могло произойти, если приятели шли по разным дорогам. Сеть дорог в городе, где живут Трурль и Клапауций, обладает следующим свойством. Где бы Трурль не устраивал засаду на Клапауция, Клапауций всегда мог пройти от своего дома до дома Трурля, не встретившись с ним.

Напишите программу, которая позволяет найти два пути между домами Трурля и Клапауция, по которым они смогли бы пройти, не встретившись.

Во входном файле в первой строке содержится два целых числа, разделенных пробелом: количество развилок в городе `N` (`3\ ≤\ N\ ≤\ 100`) и число улочек в городе `M` (`3\ ≤\ M\ ≤\ N(N-1)/2`). Далее следует M строк с описанием улочек. В каждой строке содержится два целых числа `a_i` и `b_i` (`1\ ≤\ a_i,\ b_i\ ≤\ N`, `a_i\ ≠\ b_i`, `1\ ≤\ i\ ≤\ M`), разделенных пробелом – это означает, что улочка соединяет развилки `a_i` и `b_i`. Между двумя развилками может быть не более одной улочки.

В выходной файл вывести две строки, содержащих информацию о двух найденных путях между развилками 1 и `N`, не имеющих общих точек, кроме развилок 1 и `N`. Первым числом в строке указывается длина пути `k`, далее следует (`k+1`) целое число через пробел – номера развилок, через которые проходит путь, начиная с развилки 1 и заканчивая развилкой `N`. Путь не должен содержать циклов. Если существует несколько вариантов двух путей, вывести один (любой) из них.

6 7
1 2
2 3
1 4
2 5
3 6
4 5
5 6

3 1 2 3 6
3 1 4 5 6