# 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