This is the personal work of Denis Dmitriev; it is not an officially verified or endorsed solution.

Denis writes: Actually this problem can be solved in somewhat simpler way (because of the limitations imposed on the road system), but since it's much easier and faster to code just a standard path-finding over the regular graph, this solution is more suitable for a real contest (where time is a precious resource). Effectiveness in this particular case is not of a big concern because the maximum number of vertices (26) is low enough. -DD

## C++ Source Code

```#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <deque>
#include <string>

using namespace std;

void main(void)
{
FILE *fp=fopen("rom.in","r");
FILE *fo=fopen("rom.out","w");

char name[16][2];
bool map[26][26];
memset(map,0,sizeof(map));

{
fscanf(fp,"%s %s",name[0],name[1]);

/* since all the letters but first may be ignored (remember,
* `No
* two cities begin with the same letter'), we will ignore
* them
*/
b=*name[0]-'A',e=*name[1]-'A';
map[b][e]=map[e][b]=true;
}

for(i=0;i<queries;i++)
{
deque<int> p;
string visited[26];

fscanf(fp,"%s %s",name[0],name[1]);
b=*name[0]-'A';
e=*name[1]-'A';

/* initialize deque (depth search) */
p.push_back(b);
visited[b]+=*name[0];

/* if there are still vertices in deque... */
while(!p.empty())
{
/* take the one in the beginning */
int c=p[0];
p.pop_front();

/* and check if it is possible to make a step from
* it
* to some other vertex, shortening the route from
* the
* origin to it
*/
for(j=0;j<26;j++)
{
string &v=visited[j];
/* if there is a road and the target city
* was
* not visited yet or the route through `c'
* is
* more optimal than the one already
* found...
*/
if(map[c][j]&&(v.empty()||v.size()>visited[c].size()+1))
{
/* ...move to it */
v=visited[c],v+='A'+j,p.push_back(j);
/* if the destination was
* encountered... */
if(j==e)
{
/* ...forcingly quit the
* loop */
p.clear();
break;
}
}
}
}