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