Hauling Ore

Administrator Selfridge is analyzing possible mining routes on Pandora. He has collected some data in the form of a graph. The latest ore carriers can visit exactly 3 mining camps. Your goal is to help him find out which mines may be visited from other mines with 2 stops (but not fewer).

Connections between mines are described beginning with the line ”GRAPH BEGIN”. Additional lines lists individual mines (nodes), followed (on the same line) by their neighboring mines (edges). The line ”GRAPH END” ends the list of path descriptions. The next lines list mines for which answers need to be calculated, each on a single line. Following these lines, a completely new instance of the problem can be given, starting from scratch.

Some mines may appear only as neighboring mines, without being described on a separate line. Mine names can be arbitrary strings, as long as they don’t contain any whitespace.

Your output should consist one line (for each mine analyzed), consisting of the name of the mine, followed by the mines, in alphabetical order, that can be visited with exactly 2 stops but not fewer, starting from the given mine.

GRAPH BEGIN
a b c
b c d
d e f
GRAPH END
a
b
c
d
e
f

d
e f
d
a c
b f
b e

2010 MHSPC