ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Open Personal Contest 2006

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. Buses in Vasyuki

Time limit: 1.5 second
Memory limit: 64 MB
The Vasyuki University is holding an ACM contest. In order to help the participants make their stay in the town more comfortable, the organizers composed a scheme of Vasyuki's bus routes and attached it to the invitations together with other useful information.
The Petyuki University is also presented at the contest, but the funding of its team is rather limited. For the sake of economy, the Petyuki students decided to travel between different locations in Vasyuki using the most economical itineraries. They know that buses are the only kind of public transportation in Vasyuki. The price of a ticket is the same for all routes and equals one rouble regardless of the number of stops on the way. If a passenger changes buses, then he or she must buy a new ticket. And the Petyuki students are too lazy to walk. Anyway, it easier for them to write one more program than to walk an extra kilometer. At least, it's quicker.
And what about you? How long will it take you to write a program that determines the most economical itinerary between two bus stops?
P.S. It takes approximately 12 minutes to walk one kilometer.


The first input line contains two numbers: the number of bus routes in Vasyuki N and the total number of bus stops M (1 ≤ N ≤ 1000; 1 ≤ M ≤ 105). The bus stops are assigned numbers from 1 to M. The following N lines contain descriptions of the routes. Each of these lines starts with the number k of stops of the corresponding route, and then k numbers indicating the stops are given. There are in total not more than 200000 numbers in the N lines describing the routes. In the (N+2)-nd line, the numbers A and B of the first and the last stops of the required itinerary are given (numbers A and B are never equal).


If it is impossible to travel from A to B, then output −1. Otherwise, in the first line you should output the minimal amount of money (in roubles) needed for a one-person travel from A to B, and in the second line you should describe one of the most economical routes giving the list of stops where a passenger should change buses (including the stops A and B).


3 10
5 2 4 6 8 10
3 3 6 9
2 5 10
5 9
5 10 6 9
Problem Author: Eugine Krokhalev, Ekaterina Vasilyeva
Problem Source: The 7th USU Open Personal Contest - February 25, 2006
To submit the solution for this problem go to the Problem set: 1434. Buses in Vasyuki