HUST Monthly 2011.06.26 (Personal Contest)

From: 2011-06-26 14:30:00 To: 2011-06-26 17:30:00 Now: 2017-09-22 06:52:30 Status: Public

D - Tobor and Energy Hole

Time Limit: 1s Memory Limit: 128MB

Submissions: 2 Solved: 2
Description

         As Tobor has arms, she can do many things that can not be done before. But Tobor is not happy, because the limit of energy Y.D.I give her, and, which is the most important, that she cannot move. So after some thought, Y.D.I decided to set up legs for Tobor, so that she can move to any where she want. However limited by technique, each movement of unit length need one energy stone.

         In Y.D.I’s lab, there are some Energy Holes. It’s a mysterious stuff. Each holes is connected with some sub holes by unit length bidirectionalpass, and each of these sub holes are not connected with each other. A hole can be connected without any sub holes, either. In each hole, there are some energy stones, and object cannot stay at a hole more than one second, otherwise it will be destroyed. There is many teleports in Y.D.I’s lab too, and a teleport can send an object tosomeother teleports without any energy stone. A teleport cannot send an object to itself.

         Y.D.I knows that some holes are connected and some are not, so he choose some standing holes to stands for the holes which is connected with it, and set a teleport to it.

         Note :

         a. If Hole A is one sub hole of Hole B, then we consider that B is one sub hole of A too.

         b. If Hole A is connected with Hole B, and Hole B is connected with Hole C, then we consider that Hole A and Hole C are connected.

         c. If Hole A has a teleport A, Hole B has a teleport B, and Teleport A can send object to Teleport B, then we do not consider these two Holes are connected.

         d. Every components of connected holes has only one standing hole with teleport.

         Now Tobor was send to a hole with teleport. She has a stone bag, which can only contain one Energy Stone, so at any moment Tobor can have only one Energy Stone at most. As she just have legs, she want to move as long as possible. If she move to a hole, she can get one energy stone if possible, and move to another hole immediately if she has energy stone left, or use teleport to another hole if there is a teleport in this hole. She can move to a same hole many times. Any hole with teleport can be the END of her torments.

         Tobor knows the maximum distance she can move. do you know?

         Note:

         a. Only moves by leg between holes are add to total distance, using the teleport has zero contribution to the total distance.

         b. Tobor start without any energy stone, but she can pick one energy stone from her starting hole if possible, then move by legs or use teleport. Consider the Sample.

Input

 

Multiple cases, you need process to EOF. First line contains T, H and S, where T indicates the number of teleports, H indicates the number of holes, and S indicates the initial hole Tobor is at. 0< T<=H <= 20000, S is in the range of [1, M] and S is a hole with teleport.

Every next T lines contains ID M A0 A1 … AM, where ID indicates which hole the teleport is set, M indicates the number of destination teleports it can send to, and A0 to Am describe these M destination teleports. ID is in the range of [1, H]; M is in the range of [0, T]; A0 to Amis in the range of [1, H]. Note it’s guaranteed that the destination hole has a teleport, either. Integers are split by single space.

The i+T+1 to H+i+T+1 lines describe the H holes. The i th line describe the i th Energy hole, and is formatted as:

StoneNumber N B0 B1 … BN.

Where StoneNumber indicates the number of Energy stone this Energy hole contains, N indicates the number of connected sub holes of this hole, and B0 to BN is indicates the id of connected sub holes. StoneNumber is in the range of [0, 1000]; N is in the range of [0, H-1]; B0 to BN is in the range of [1,H]. Integers are split by single space.

Output

 

Print case number first, and print the maximum distance Tobor can move. See Sample Output.

Sample Input
2 5 1
1 1 4
4 0
1 2 2 3
5 1 1
5 1 1
5 1 5
0 1 4
Sample Output
Case 1:
2
Hint

For more information, please download the problems in zip or pdf.

Any question please mail to dy0013@163.com.

Source
idy0013@gmail.com