SP10447 CONTCITY - Contaminated City

In a far away country there is a city facing a big problem. The city is plagued by a deadly gas. Many people have died, but there are groups of survivors at places around the city. Between these places there are roads connecting two distinct places that can still be traversed safely. These roads can be traversed in both directions. It's known the number of days necessary to traverse each road and the two places that it connects. It's also known the number of survivors at each location. Each survivor can get to other places following a sequence of roads. The mayor will send several helicopters to rescue these people, each having a capacity, a limit on the number of crew (people that it can rescue). Each helicopter will land on a certain day and place. You should answer an important question for the mayor. How many days are needed to rescue all survivors? If it's not possible to rescue all people you should answer how many of them can be rescued.

The first line of input file have the number of test cases T (T

For each test case there is one line in output. If all people can be rescued "All people can be rescued in D day(s) ." should be printed, where D is the minimum number of days to rescue all people. If it is impossible to rescue all people "X survivor(s) can be rescued." should be printed, where X is the maximum number of survivors that can be rescued.