Travel Agency

Holger works at a travel agency in Germany. Frequently, Holger is asked to recommand a route that goes from one city to a second city using Germany's Autobahn system. Holger has decided that the best way to answer this question is to find the route that minimizes the number of Autobahn segments between the two cities.

For example, if someone asks Holger how to go from Leipzig to Frankfurt and Holger knows about one route that goes from Leipzig to Berlin to Frankfurt (two segments) and one route that goes from Leipzig to Halle to Fulda to Frankfurt (3 segments), Holger will tell the customer about the first route.

For this problem, you will help Holger by writing a computer program to automate the process.

Input File

The first number in the input file is a positive integer no larger than 100, n, that tells how many cities are connected by the Autobahn. For simplicity, the cities are represented by the numbers 0 through n-1.

The next portion of the input file shows direct Autobahn connections between pairs of cities. For each pair of cities, (x, y), you may assume that x and y are not equal and 0 ≤ x, y ≤ n-1. The pair (-1, -1) indicates the end of this section of the input file. On all segments of the Autobahn, cars can move in both directions.

The final portion of the input file contains an unknown number of queries. Each query consists of a pair of integers, (x, y), where 0 ≤ x, y ≤ n-1. If it is possible to go from city x to city y, the message The route between city x and city y has k segments should be printed where k is the smallest number of segments possible. If it is not possible to go from city x to city y, the message The route between city x and city y does not exist should be printed.

Sample Input File: routes.in

10
1 4
4 5
5 6
9 4
9 7
7 4
3 2
7 2
-1 -1
0 8
4 0
1 1
1 4
1 5
1 6
7 1
2 1
3 1
9 1

Sample Output File: routes.out

The route between city 0 and city 8 does not exist
The route between city 4 and city 0 does not exist
The route between city 1 and city 1 has 0 segments
The route between city 1 and city 4 has 1 segments
The route between city 1 and city 5 has 2 segments
The route between city 1 and city 6 has 3 segments
The route between city 7 and city 1 has 2 segments
The route between city 2 and city 1 has 3 segments
The route between city 3 and city 1 has 4 segments
The route between city 9 and city 1 has 2 segments