IPST59: Delivery

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int L = 10 + 5;
const int logN = 16;

map<int, int> tmpL, tmpR;
vector<pii> linkage, sideL, sideR;
int ex, rnk[1 << logN], idx[L], mat[L][L], LCAdist[2][L];

int LCAsideL(int u, int v){
    int sum = 0;
    if(rnk[u] < rnk[v]){
        swap(u, v);
    }
    for(int e = ex - 1; e >= 0; --e){
        if(rnk[u >> e] >= rnk[v]){
            u = u >> e;
            sum += e;
        }
    }
    if(u == v){
        return sum;
    }
    for(int e = ex - 1; e >= 0; --e){
        if((u >> e) != (v >> e)){
            u = u >> e;
            v = v >> e;
            sum += e + e;
        }
    }
    sum += 2;
    return sum;
}
int LCAsideR(int u, int v){
    return LCAsideL(u - (1 << ex), v - (1 << ex));
}

bool isL(int u){
    return u < (1 << ex);
}

int dist(int u, int v){
    if(isL(u) && isL(v)){
        return LCAsideL(u, v);
    } else if(!isL(u) && !isL(v)){
        return LCAsideR(u, v);
    }
    return 1e9;
}

int main(){

    int nLink, Q;
    scanf("%d%d%d", &ex, &nLink, &Q);

    rnk[0] = -1;
    for(int e = 0; e < ex; ++e){
        for(int i = (1 << e); i < (1 << (e + 1)); ++i){
            rnk[i] = e;
        }
    }

    int cNodeCnt = 0;
    for(int i = 1; i <= nLink; ++i){
        int u, v;
        scanf("%d%d", &u, &v);
        if(u > v){
            swap(u, v);
        }
        linkage.emplace_back(u, v);
        if(tmpL.find(u) == tmpL.end()){
            tmpL[u] = ++cNodeCnt;
            idx[cNodeCnt] = u;
        }
        if(tmpR.find(v) == tmpR.end()){
            tmpR[v] = ++cNodeCnt;
            idx[cNodeCnt] = v;
        }
    }
    for(int u = 1; u <= cNodeCnt; ++u){
        for(int v = 1; v <= cNodeCnt; ++v){
            if(u == v){
                mat[u][v] = 0;
            } else {
                mat[u][v] = 1e9;
            }
        }
    }
    for(pii p : tmpL){
        sideL.push_back(p);
    }
    for(int i = 0; i < (int)sideL.size() - 1; ++i){
        for(int j = i + 1; j < sideL.size(); ++j){
            int u = sideL[i].second;
            int v = sideL[j].second;
            int w = LCAsideL(sideL[i].first, sideL[j].first);
            mat[u][v] = w;
            mat[v][u] = w;
        }
    }
    for(pii p : tmpR){
        sideR.push_back(p);
    }
    for(int i = 0; i < (int)sideR.size() - 1; ++i){
        for(int j = i + 1; j < sideR.size(); ++j){
            int u = sideR[i].second;
            int v = sideR[j].second;
            int w = LCAsideR(sideR[i].first, sideR[j].first);
            mat[u][v] = w;
            mat[v][u] = w;
        }
    }
    for(pii p : linkage){
        int u = p.first;
        int v = p.second;
        u = tmpL[u];
        v = tmpR[v];
        mat[u][v] = 1;
        mat[v][u] = 1;
    }

    for(int k = 1; k <= cNodeCnt; ++k){
        for(int u = 1; u <= cNodeCnt; ++u){
            for(int v = 1; v <= cNodeCnt; ++v){
                if(mat[u][k] + mat[k][v] < mat[u][v]){
                    mat[u][v] = mat[u][k] + mat[k][v];
                }
            }
        }
    }

    while(Q--){
        int u, v;
        scanf("%d%d", &u, &v);
        int mn = dist(u, v);
        for(int i = 1; i <= cNodeCnt; ++i){
            LCAdist[0][i] = dist(u, idx[i]);
            LCAdist[1][i] = dist(v, idx[i]);
        }
        for(int i = 1; i <= cNodeCnt; ++i){
            for(int j = 1; j <= cNodeCnt; ++j){
                if(i == j){
                    continue;
                }
                mn = min(mn, LCAdist[0][i] + mat[i][j] + LCAdist[1][j]);
            }
        }
        cout << mn << '\n';
    }

    return 0;
}