PROBMOR - Problems in Moria

Balin, in his last days, needed to put more workers on the tunnels of Moria to build a lot of shelters to his people and to discovery the depths of that land. However, he didn't know where to put a collection point in order to take all the rocks in the way and bring all of them outside of Moria. The only thing he knew was this collection point needed to be fix in a junction point that connects two independent parts. If there's no point with this feature, any junction point, that's not the source one, can be used.

Input

The input contains several test cases. Each test is given by a line with two integers X (0 < X ≤ 100) and Y (0 < Y). The first one is the number of points and the second, the number of tunnels. Then, the next Y lines are followed by three integers: A (0 < A ≤ 100), B (0 < B ≤ 100) and C (0 < C), which means, there's a link between A and B with a capacity C of workers that can walk through there. After that, there's a line with only one integer which is the start point, in the other words, the point where the workers are divided.

Output

For each test case, display its case number followed by a blank line. In the next line display the number Z of points that can be used as a collection point and, in the next Z lines shows in decreasing order the maximum number of workers that can be used. Each test case is separated by a blank line as the sample output.

Example

Input:
45
125
148
233
2 4 11
346
1
56
125
148
233
2 4 11
346
4 5 12
2

Output:
Case 1

Points: 3
13
13
9

Case 2

Points: 1
19


Added by:Paulo Costa
Date:2012-02-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:UFAM

hide comments
2012-02-10 17:51:57 Renato Parente
is the graph connected?
2012-02-10 17:25:16 timedoita
Is there a blank line after the last test case?
2012-02-10 16:29:02 Mateus Dantas [ UFCG ]
Never...The source point never can be used as a collection point.
2012-02-10 16:23:22 Andrés Mejía-Posada
Can you sometimes use the source junction point as the collection point? Or never?
2012-02-10 16:14:59 Mateus Dantas [ UFCG ]
Yes, it's a Bidirected graph..
2012-02-10 16:04:41 Los Desempleados FIIS
Can tunnels be used in any direction?

Last edit: 2012-02-10 16:04:55
2012-02-10 15:34:25 Suit up!
Please, could you describe why the last test case the answer is 19? Thank you![2]
Same question.
2012-02-10 15:25:50 Dona Margarida
Please, could you describe why the last test case the answer is 19? Thank you!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.