Acquapia is a small country crossed by several rivers, all of them navigable. All rivers have their sources inside Acquapia, in the mountains, and all rivers end at sea – a river never ends at another river. During its course (not at its source) a river may split into two or more streams. There is a city wherever a river begins, splits or ends, and each city touches at most one river. The figure below shows a map of Acquapia, with two rivers and twenty cities. For clarity, only some cities are labeled. In the figure, E and F are cities that have river sources; B, C and D are cities where a river splits into different streams; and A is a city where a river ends.
Being so widespread, rivers are the main means of transportation in Acquapia. But since the country is at war with a neighboring country, it is not safe for ships to cross the sea, so ships can only navigate in rivers. That means that to go from city A to city D, a ship must travel upstream (against the river flow) from A to B and C, make a stream change at C and then travel downstream from C to D. Stream change, which is the operation of changing from navigating upstream to navigating downstream, is difficult and somewhat dangerous, since river streams are strong in Acquapia, and the turns are sharp. Notice that to navigate from B to E (or from E to B) no stream change is necessary. Also, due to the war, it is not possible to navigate, for example, from B to F.
Acquapia Cargo Management (ACM) is a software house that specializes in systems for navigation. ACM wants you to write a program that, given the description of rivers, the description of cities, and a set of queries, each composed by a pair of cities X and Y , answer the following questions:
• “now that ships cannot cruise the sea, is it possible to navigate from city X to city Y ”?
• “if it is possible to navigate from X to Y , does a ship need to make a stream change? If so, in which city, so that the distance travelled is the shortest possible?