Lets Do Lunch

A short programming exercise

Peggy Piranha and Samuel Amherst Salmon III (Sam) are old friends looking to get together for lunch. They havent seen each other in ages, but are keen on crossing paths for lunch. But where could they meet? Theyre flexible on the ultimate destination, but there are few constraints.

Peggy and Sam live in a fairly complicated watershed, with many rivers running together and splitting apart. Sam has to keep moving upstream for spawning season. Peggy has dinner plans with a killer whale later in the day, and has to keep moving downstream. Fortunately, we have a map given to us by the Piscine Post Office, with each junction marked with an address. Each segment of river is listed as pairs of addresses, from upstream to downstream. Given the map and a list of possible starting locations for Peggy and Sam, give the list of locations where they could meet. Oh, and there are a few places they must avoid passing through, with waterfalls, rapids, and other unpleasantness. Your job is to list the possible addresses where they could meet, one per line and sorted alphabetically by address.

Input/Output

Input and output are simple text, via standard input and standard output, respectively. Input will be provided in the format shown in the example below: the list of address pairs forming the map, followed by the list of addresses to avoid, the list of possible starting locations for Peggy, and finally the list of possible starting locations for Sam.

Input

Map:

a1 b1

a2 b1

a2 b2

a2 b3

b1 c1

b2 c2

b2 c3

b3 c3

Avoid: b2

Peggy: a2

Sam: c2 c3

ourput

a2

b3

c3

this is java mapping i