Дано N городов, соединенных между собой дорогами(на рис. показано что 1 город связан со 2, 3 и 4 городами, 3 город связан с 4 и 7 городами, 4 связан с 6, 5 связан с 6 и 7 городами, а 6 связан с 7!!! Связан - т.е. между ними есть дорога!
Входные данные:
В первой строчке вводится количество городов N.
Во второй строчке вводится количество соединений между городами K.
В каждой следующей i-той строке (i<=K) вводится пара номеров городов через пробел соединенных городов.
В последней строке вводится пара номеров городов(через пробел), для которых необходимо найти все возможные маршруты, ведущие от одного города к другому.
Выходные данные:
В первой строке выводится число равное количеству найденных маршрутов.
В каждой последующей выводится последовательность номеров городов разделенных пробелами, являющаяся очередным маршрутом.
Номера городов в одном и том же маршруте не должны повторятся.
Пример:
Входные данные:
7
9
1 2
1 3
3 4
3 7
4 6
5 6
5 7
6 7
1 7
Выходные данные:
4
1 3 7
1 4 3 7
1 4 6 5 7
1 4 6 7