SPOJ Problem Set (classical) 10586. Problems in Moria Problem code: PROBMOR

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 Y 0 . 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 e C C0 , 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 it's 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
Languages:	All
Resource:	UFAM