Задача D. Прогулка
Задачу добавил: alef
Успешно сдано решений: 5
Маша любит кататься на велосипеде, а Витя предпочитает роликовые коньки. Они собираются проехать из пункта A в пункт B (ну, например, от Загородного парка до Речного вокзала:)). К сожалению, в городе нет велодорожек, да и асфальтовое покрытие ряда улиц не очень располагает к езде на роликовых коньках.
Маша и Витя хорошо знают город и составили план, на котором показана возможность проехать по тому или иному участку пути на велосипеде и / или роликовых коньках. На этом плане указаны N точек (включая A, имеющую #1, и B, имеющую #N) и соединяющие их линии. Между любыми двумя точками существует не более одной линии. Для каждой линии указано, можно ли передвигаться между точками, которые она соединяет, на велосипеде, на роликовых коньках или же и на том, и на другом «виде транспорта». Если точки соединены линией непосредственно, то перемещение между ними и у Маши, и у Вити занимает ровно одну единицу времени.
Поскольку в пункте B (на Речном вокзале) они уговорились встретиться с Петей, они хотели бы добраться туда максимально быстро, а значит, каждый из них должен двигаться по кратчайшему (для себя) пути. При этом Маша и Витя хотят как можно большую часть пути ехать вместе.
Ваша задача — найти такие два кратчайших пути (один для езды на велосипеде, а другой — для езды на роликах), которые имеют наибольшее количество общих отрезков.
Формат входного файла input.txt
Первая строка — целое число N (2 <= N <= 100) — количество точек на плане.
Вторая строка — целое число V — количество пар точек, которые соединены дорогой, пригодной для проезда велосипеда
Каждая из следующих V строк задает одну такую пару точек: два числа через пробел
Следующая строка — целое число R — количество пар точек, которые соединены дорогой, пригодной для проезда на роликах.
Каждая из следующих R строк задает одну такую пару точек: два числа через пробел.
Если из точки #J можно проехать в точку #K, то проехать из точки # K в точку # J также можно. Гарантируется, что и Маша, и Витя могут добраться из точки A в точку B.
Формат выходного файла output.txt
Первая строка — целое число, максимально возможное количество общих отрезков на пути Маши и Вити.
Вторая строка содержит целое число — количество точек, через которые пролегал путь Маши, а затем через пробел — последовательность номеров точек (через пробел), через которые пролегал путь Маши
Третья строка содержит целое число — количество точек, через которые пролегал путь Вити, а затем через пробел — последовательность номеров точек (через пробел), через которые пролегал путь Вити
Точки #1 и #N должны быть включены в эти пути (как начало и конец последовательности номеров точек)
Пример входного файла — 1
5
4
1 2
2 3
3 4
4 5
3
1 2
2 4
4 5
Пример выходного файла — 1
1
5 1 2 3 4 5
4 1 2 4 5
Пример входного файла — 2
21
15
1 2
2 3
3 4
4 6
6 8
8 10
10 20
20 21
2 13
13 14
14 15
15 16
16 17
17 18
18 21
15
1 2
2 3
3 5
5 7
7 9
9 11
11 20
20 21
2 12
12 14
14 15
15 16
16 17
17 19
19 21
Пример выходного файла — 2
4
9 1 2 13 14 15 16 17 18 21
9 1 2 12 14 15 16 17 19 21