1575. Yekaterinburg Subway 2

      #include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<map>

#include<vector>

#include<stack>

#include<set>

#include<map>

#include<queue>

#include<algorithm>

#include<cmath>

#define LL long long

#define sint short int

//#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

const int N=105;

const int INF=0x3f3f3f3f;

string s[10][N]={

    {"7_klyuchey", "Sortirovochnaya", "China_town", "Zarechny", "City", "1905_year_square", "Kuybyshevskaya",

        "Sibirskaya", "Siniye_kamni", "Lechebnaya", "Varshavskaya", "Kompressornaya", "Koltsovo"},

    {"Zelyony_ostrov", "Tatishchevskaya", "Verh_Isetskaya", "Kommunarov_square", "1905_year_square",

        "Teatralnaya", "Vostochnaya", "Vtuzgorodok", "Kamennye_palatki", "University"},

    {"MEGA", "Metallurgov", "Kraulya", "Central_stadium", "Moskovskaya", "1905_year_square",

        "Shevchenko", "Pionerskaya", "Turbinnaya", "Elmash", "Taganskaya"},

    {"Akademicheskaya", "Yugo_zapadnaya", "Volgogradskaya", "Posadskaya", "Geologicheskaya", "Teatralnaya",

        "Gagarinskaya", "Komsomolskaya", "Shefskaya", "Ozyornaya", "Italyanskaya", "Kalinovskaya"},

    {"Sovhoznaya", "Voennaya", "Aviatsionnaya", "Dvorets_sporta", "Geologicheskaya",

        "Kuybyshevskaya", "Vostochnaya", "Gagarinskaya", "Vilonovskaya"},

    {"Keramicheskaya", "Vtorchermet", "Samolyotnaya", "Botanicheskaya", "Parkovaya", "Mayakovskaya",

        "Oborony_square", "Kuybyshevskaya", "Teatralnaya", "Shevchenko", "Uralskaya", "Zvezda",

        "I_Pyatiletki_square", "Pobedy"},

    {"Himmash", "Nizhne_Isetskaya", "Uktusskie_Gory", "Shcherbakovskaya", "Botanicheskaya", "Chkalovskaya",

        "Bazhovskaya", "Geologicheskaya", "1905_year_square", "Dinamo", "Uralskaya", "Mashinostroiteley",

        "Uralmash", "Prospekt_Kosmonavtov", "Bakinskih_Komissarov"},

    {"Moskovskaya", "Kommunarov_square", "City", "Uralskaya", "Pionerskaya", "Gagarinskaya", "Vtuzgorodok",

        "Sibirskaya", "Oborony_square", "Bazhovskaya", "Dvorets_sporta", "Posadskaya", "Moskovskaya"}

};

int L[10]={13,10,11,12,9,14,15,13};

int a[N];

map<string,int>mt;

int dist[N][N];

int main()

{

    //freopen("data.in","r",stdin);

    for(int i=0;i<N;++i)

    for(int j=0;j<N;++j)

    dist[i][j]=INF;

    int k=0;

    for(int i=0;i<8;++i)

    {

        for(int j=0;j<L[i];++j)

        {

            if(mt.find(s[i][j])==mt.end())

            {

                mt[s[i][j]]=k++;

            }

            a[j]=mt[s[i][j]];

        }

        for(int j=1;j<L[i];++j)

        {

            dist[a[j]][a[j-1]]=1;

            dist[a[j-1]][a[j]]=1;

        }

        if(i==7)

        {dist[a[0]][a[L[i]-1]]=1;dist[a[L[i]-1]][a[0]]=1;}

    }

    for(int i=0;i<k;++i)

    dist[i][i]=0;

    for(int l=0;l<k;++l)

    for(int i=0;i<k;++i)

    for(int j=0;j<k;++j)

    if(dist[i][l]+dist[l][j]<dist[i][j])

    dist[i][j]=dist[i][l]+dist[l][j];

    int n;

    cin>>n;

    while(n--)

    {

        string s1,s2;

        cin>>s1>>s2;

        cout<<dist[mt[s1]][mt[s2]]<<endl;

    }

    return 0;

}