Many tourists like to see and experience as much as possible in their travels. Consequently, the Visitors Information Bureau on the Kyere Islands has set up a hot line on which tourists can call in and ask for a circuit route to drive on a round trip between any two towns on an island. You are to write a program that determines whether or not it is possible to drive between two designated towns, and, if that is possible, to determine whether or not a circuit route exists between the two towns. A circuit route goes from the first town to the second and back to the first without traversing twice any road segment between any towns. Tourists are especially interested in circuit routes because they provide the greatest opportunity for sightseeing. It should be obvious that the presence of a circuit route for two towns means that two or more distinct routes (with no common road segments) exist between the towns.
For simplicity, the towns in the Kyere Islands are labeled with a single letter - A through Z. The input data for your program consists of a list of road segments, one per line. For example, the data line BT indicates there is a road segment between town B and town T; it may be traversed in either direction. A data line in which the two towns are the same marks the end of the road segments. Following this are a series of tourist queries, consisting of two town labels, again ending with a data line in which the two towns are the same. For example, the query line CH is a request to find a circuit route from town C to town H. Your program should respond with one of three messages:
No route from C to H Route: C...H All routes from C to H have at least one common road segment Route: C...H Route: C...H Two or more distinct routes from C to H
where ... is replaced with the sequence of towns passed through between C and H. The routes shown for the second and third messages depend on the road segment data. The two routes given for the third message use different road segments.
Following is a sample listing of input data, the road network that the data represents, and possible output for the queries given.
Input data: Road Network AD CD A ER CV AV V C D TA PE XR T M S MV SM KS K TV MT KM JJ X R AS ET PR E P DM XX Output Route: ATMS Route: ADCVMKS Two or more distinct routes from A to S No route from E to T Route: PER All routes from P to R have at least one common road segment Route: DATM Route: DCVM Two or more distinct routes from D to M
The queries are the input values that follow the JJ entry, namely, AS, ET, PR, and DM.