The world is full of tourist guides, so here's another tourist guide challenge for you. This time it's about Bruno, a shady guy with a car who has promised to drive you around town.

What he didn't tell you before is that besides being a shady character, he's also a pretty shit driver. He has a lot of traffic fines to pay and is eager to avoid having to pay more. He therefore wants to know where all the police cameras are located so he can drive more carefully when passing them. These cameras are strategically distributed over the city, in locations that a driver must pass through in order to drive from one zone of the city to another. A location C will have a camera if and only if there are two city locations A and B such that all paths from A to B pass through C.

For instance, suppose that we have six locations (A, B, C, D, E, and F) with seven bidirectional routes B-C, A-B, C-A, D-C, D-E, E-F, and F-C. There must be a camera on C because to go from A to E you must pass through C. In this configuration, C is the only camera location.

Given a map of the city, help Bruno out by writing a program to identify where all the cameras are.


The input will consist of an arbitrary number of city maps, where each map begins with an integer \(2 < N \leq 100\) denoting the total number of locations in the city. Then follow \(N\) differten place names at one per line, where each place name will consist of at least one and at most 30 lowercase letters. A non-negative integer \(R\) then follows, denoting the total number of routes in the city. The next \(R\) lines each describe a bidirectional route represented by the two places that the route connects.

Location names in route descriptions will always be valid, and there will be no route from one place to itself. You must read until \(N=0\), which should not be processed.


For each city map you must print the following line:

City map #d: c camera(s) found

where \(d\) stands for the city map number (starting from 1) and \(c\) stands for the total number of cameras. Then should follow \(c\) lines with the location names of each camera in alphabetical order. Print a blank line between output sets.

Sample Input

ipanema copacabana
copacabana sugarloaf
ipanema sugarloaf
maracana lapa
sugarloaf maracana
corcovado sugarloaf
lapa corcovado
guanabarabay sambodromo
downtown sambodromo
sambodromo botanigarden
colombo sambodromo

Sample Output

City map #1: 1 camera(s) found

City map #2: 1 camera(s) found

This is challenge 10199 of the ACM International Collegiate Programming Contest. Test input is provided by uDebug.

Upload Solution

Please log in to submit your solution.


Difficulty (2 votes)
Average test runtime 0.35
Points (changes over time) 10
Tried by 2 users
Solved by 2 users

Global ranking

# Name Runtime Points worth
1 贝尔恩德 0.22 14
2 Mac 0.47 6