В некоторой стране протянута сеть железных дорог. Требуется наладить сообщение между двумя различными городами A и B, пустив наибольшее возможное число поездов от A до B. Из-за конструктивных особенностей поездов, нарушений расписания и прочих объективных причин необходимо, чтобы никакие два поезда не проезжали через один город, за исключением,
конечно, городов A и B.
Входные данные
В первой строке записаны целое число M - количество городов в стране (2 ? M ? 25) и номера городов A и B (города нумеруются числами от 1 до M). Далее перечислены все железные дороги страны, каждая из них задается парой номеров городов, которые она соединяет. Все дороги считаются одноколейными и ориентированными, то есть ведущими из первого города пары во второй, но не наоборот.
Выходные данные
Выведите в первую строку выходного файла целое число K - максимальное количество поездов, которые можно пустить из A в B. Далее выведите K маршрутов поездов, по одному в каждой строке. Каждый маршрут задается номерами городов, через которые проходят поезда в порядке следования от A до B.
Пример входного файла
5 2 4
2 1
2 3
1 3
3 1
1 4
3 4
3 5
Пример выходного файла
2
2 1 4
2 3 4
|
