All Roads Lead Where?

There is an ancient saying that "all roads lead to Rome." If that were literally true, finding a route between any two cities would be easy: to travel from city $A$ to city $B$, go from $A$ to Rome and then from Rome to $B$. Of course, a shorter route often exists.

The road network of the Roman Empire had a simple, tree-like structure. Starting at Rome, several roads led out to nearby cities. From those cities, more roads led to cities farther away, and so on. The cities can therefore be pictured as lying in levels around Rome: a city in level $i$ is connected only to cities in level $i-1$ and level $i+1$, with Rome alone at level $0$. The network contains no cycles. Every city in level $i$ is connected to exactly one city in level $i-1$ (its unique neighbor closer to Rome) and to zero or more cities in level $i+1$. As a result, the network forms a tree rooted at Rome, and there is exactly one simple route between any two cities.

Given such a network of roads and cities, find the shortest route between two given cities, where the length of a route is the number of cities along it.

The first line contains two integers separated by a single space: $m$, the number of roads in the network, and $n$, the number of queries.

Each of the next $m$ lines contains the names of two cities separated by a single space, describing one road. A city name has at most ten letters and starts with an uppercase letter; no two cities share the same first letter. The city named Rome always appears and is the level-$0$ city. On every road line the first city lies in a lower-numbered level than the second city (that is, the first city is the second city's neighbor toward Rome). No road line is repeated, and the network obeys the tree structure described above.

Each of the next $n$ lines contains the names of two cities separated by a single space; these are the query pairs. For each pair, report the shortest route from the first city to the second. Both cities of every query are guaranteed to appear among the roads, and a city is never paired with itself.

For each of the $n$ queries, output one line describing the shortest route between the two cities of that pair. Because the network is a tree, this route is unique. Write the route as the first letters of the cities along it, from the first query city to the second (including both endpoints), as consecutive uppercase letters with no spaces. The $k$-th output line corresponds to the $k$-th query.