Minimal
Path
Gigi, the business man, must reach the city no j, in order to sign an important
business agreement. However, before siginng the agreement, he has to visit city
no i, where he has some other
important business. Since his schedule is very busy, Gigi wants to make the
whole trip using the least amount of time. That's why he would like to know the
minimum length of a trip which starts from city no 1 (the city where Gigi
lives), goes through city no i and ends up in city no j. Moreover, he would also like to know how many different paths
of minimum length exist and which some of these paths are.
Input
Data
The input file PATH.IN will contain
on the first line 4 integers, separated by blanksL N M i and j, meaning the
total number of cities in the country Gigi lives in, the total number of
bidirectional roads which connect these cities, the city Gigi has to go through
and the city where Gigi wants to finish his journey. The next M lines will
contain 2 integers: a and b, separated by a blank,
meaning that there is a road connecting cities a and b (a<>b).
Output
Data
The first line of the output file PATH.OUT will contain
the integer number L, meaning the
minimum length of Gigi's path. The second line will contain the total number of
different paths of minimum length. The next lines will contain some of the
different paths Gigi may take. If there are less than 100 different paths, then
print all of them. Otherwise, you only have to print 100 of these paths. A path
will be described as a succession of cities, separated by blanks: 1 .. i .. j (city no 1 has to be
first, city no i must be somewhere in on the path and the path must end wth
city no j).
Limits
& Clarifications
·
3 <= N <= 100
·
1 < i,j <= N ; i<>j
·
2 <= M <= N*(N-1)/2
·
The length of every road is 1. Therefore, the
descripton of a path will contain L+1 cities (not necessarily different), where
L is the minimum length of the whole path.
·
The number of different minimum length paths
will be a number between 1 and 2.000.000.000
·
The score for every test case will be
distributed as follows:
-
15 % , if the minimum length is correct.
-
50 % , if the number of different minimum length paths
is correct
-
35 % , if there are enough paths printed in the output
file, all the paths are correct, have minimum
length and any two of them are different.
·
Gigi is allowed to go through city no j, before
reaching city no i for the first time. However, the path must still end in city
no j (so he will have to come back again after visiting city no i).
·
Gigi may travel between two cities, only if
there is a road connecting them.
Example
PATH.IN PATH.OUT
7 8 7 4 6 (this is the minimum length)
1 2 8 (this is the number of different minimum
length paths)
1 3 1
2 4 5 7 5 4
2 4 1
2 4 5 7 6 4
3 4 1
2 4 6 7 5 4
4 5 1
2 4 6 7 6 4
4 6 1
3 4 5 7 5 4
5 7 1
3 4 5 7 6 4
6 7 1
3 4 6 7 5 4
1
3 4 6 7 6 4
Time limit: 0.25
seconds/test case