Task 3 - Trip

Round Trip


Your team decided to take a round trip in the host country after the competition. You want to travel to a destination city and return to the starting city. The only requirement your team specified is that the forward route to the destination city and the return route back to the starting city must contain the least possible number of common roads. (A route can not contain any road twice or more times.)

You are to write a program that computes two routes between the starting city and the destination city so that the number of common roads in the two routes is as small as possible.


The first line of the file trip.in contains two integers, S and D (S <> D), the labels of the starting and the destination cities, respectively. The second line contains two integers, N and M, where N (3<= N<= 1000) is the number of the cities and M (2<= M <= 100000) is the number of the roads between the cities. The cities are labeled from 1 to N. Each of the next M lines in the file contains two integers, P and Q (1<= P, Q <= N, P <> Q), meaning that there is a two-way road between city P and city Q. There is at most one road between any two cities.


The first line of the file trip.out must contain one integer, the least possible number of common roads of the forward and the return routes. The second line should contain a forward route as a sequence of city labels, including the starting and ending city. The third line should contain a return route as a sequence of city labels (again including the starting and ending cities). If there are more possible pairs of routes with the same least number of common roads then your program may output any one of them. If there is no route from the starting city to the destination city then the first and only line must contain -1.




1 6

7 8

2 1

1 3

2 3

4 2

4 5

5 6

7 5

6 7


1 3 2 4 5 7 6

6 5 4 2 1


If the first line of the output file contains the correct answer then you obtain 2 points. If the first line contains a correct solution and the second and third lines contain correct routes then you obtain 3 additional points.