Facebook Hacker Cup 2015 Round 3
The residents of Townsville have made it clear to the mayor that they're greatly concerned about gentrification, a process by which wealthy people move into the city in large numbers, displacing the people who currently live there. The mayor of Townsville knows a thing or two about this, and she would like to put the people's minds at ease by determining the worst-case scenario.
Townsville is made up of neighbourhoods, with one-way roads running between them. The road runs from neighbourhood to neighbourhood . A swarm of rich migrants will move to the city all at once, immediately gentrifying any neighbourhood they decide to move into.
The mayor knows the following facts about these new affluent residents: First, they like to visit other gentrified neighbourhoods. If there's a way of getting from their home neighbourhood to another gentrified neighbourhood, they will surely go visit. Second, they never walk anywhere; they only drive. Consequently, they'll get very angry if they end up in some neighbourhood with no way to drive back home.
Putting these facts together, it means that if rich migrants move into and gentrify any two neighbourhoods and , then it must be the case that there is a series of roads connecting to if and only if there is a series of roads connecting to .
Given this self-imposed constraint, and the layout of the roads in Townsville, what is the maximum number of neighbourhoods that can be gentrified?
Input begins with an integer , the number of test cases. For each test case, there is first a line containing the space-separated integers and .
Then, lines follow, the of which contains the space-separated integers and .
For the test case, print a line containing
Case #i: followed by the maximum possible number of gentrified neighbourhoods.
Explanation of Sample
In the first test case, you can get from any neighbourhood to any other neighbourhood, so they can all be gentrified.
In the second test case, any single neighbourhood can be gentrified, but that's it. If any two neighbourhoods are gentrified, there would be a path from one to the other, but no path back.
5 4 4 0 1 1 2 2 3 3 0 4 3 0 1 1 2 2 3 6 6 0 1 1 0 2 3 3 2 4 5 5 4 6 8 0 1 1 0 2 3 3 2 4 5 5 4 0 2 1 4 4 4 0 1 0 2 1 3 2 3
Case #1: 4 Case #2: 1 Case #3: 6 Case #4: 4 Case #5: 2
This work is licensed under a Creative Commons Attribution-NonCommercial 3.0 Unported License.