Hi guys

I got a CHALLENGE here, below question is From the ACM South Pacific Regional Programming Contest 2009. It is a bit long reading, hope you have some patience.Will anyone be able to tell me pseudo code indicating how to solve it?Thanks a lot

The motivation for this problem is a directionally impaired friend, who doesn't care about the shortest or quickest routes -- instead, easier is better. Your task is to read the map information from a database of the entire country and produce the route with the smallest number of roads to use for a trip between an origin city and a destination city. You are guaranteed that there will be a path between origin and destination for any query asked.

Input

The input consists of multiple cases. The input for each case consists of three

sections: the first lists the cities, the second lists the roads, and the third lists the

queries. Each case starts with an integer C (1 <= C <= 200) that represents the

number of cities, followed by C lines each containing the name of a city. There is no white space in a city's name.

The next line consists of an integer R (1 <= R <= 100) that represents the number of roads followed by R lines each describing a road. Each road description has the following form:

<RoadName> <CityA> <AB Distance> <CityB>[ <BC Distance> <CityC>[…]]

There is no white space in a road's name. Roads may pass through any number of cities. The cities appear in the order the road passes through them, and no road passes through the same city more than once. Roads are bidirectional. The

distance (an integer number) it takes to follow a road between each pair of cities is the distance listed between these two names.

The next line consists of an integer Q (1 < Q < 100) that represents the number of queries followed by Q lines each describing a query. Each query description has the following form: <origin> <destination>, where <origin> and <destination> are the names of cities.

A case with C equals zero (0) terminates the input data, and should not be processed.

Output

For each query, the output consists of a single line of the following form:

Number of roads needed from <origin> to <destination> is <number>.

<origin> and <destination> are the names of cities, and <number> is the smallest

number of roads needed for the trip.

Sample Input

5

Adelaide

Melbourne

Sydney

WestSydney

Brisbane

4

OR Adelaide 300 Melbourne

HH Melbourne 850 WestSydney 105 Sydney

M7 WestSydney 1130 Brisbane

BushTrack Adelaide 2448 Brisbane

1

Adelaide Brisbane

0

Output for the Sample Input

Number of roads needed from Adelaide to Brisbane is 1.

Explanation

The Bush Track connects Adelaide and Brisbane, so it is the only road needed.

Note that if there were only 3 roads (OR, HH and M7), all 3 would need to be used.

The traveller would have to take OR from Adelaide to Melbourne, HH from

Melbourne to WestSydney, then M7 from WestSydney to Brisbane.