o59_oct_c1_delivery

#include <bits/stdc++.h>

using namespace std;

vector <int> g[262155];
const int INF = 2e9;
using pi = pair <int, int>;
int N;
int level[262155];
vector <int> imp;
vector < vector <int>> dis(20, vector <int> (262155, INF));
vector < vector <bool>> visited(20, vector <bool> (262155, false));

void setting(int k){
    for(int i = 1; i < 1<<(k-1); i++){
        g[i].push_back(2*i);
        g[2*i].push_back(i);
        g[i].push_back(2*i + 1);
        g[2*i + 1].push_back(i);
        g[i+N/2].push_back(2*i+N/2);
        g[2*i+N/2].push_back(i+N/2);
        g[i+N/2].push_back(2*i+1+N/2);
        g[2*i+1+N/2].push_back(i+N/2);
    }
    for(int i = 1; i < 1<<k; i++)
        level[i] = level[i/2] + 1;
}

void distance(int i){
    priority_queue <pi, vector <pi>, greater <pi>> pq;
    pq.push({0, imp[i]});
    dis[i][imp[i]] = 0;
    while(pq.size() > 0){
        int u, d;
        d = pq.top().first;
        u = pq.top().second;
        pq.pop();
        if(visited[i][u])
            continue;
        visited[i][u] = true;
        for(auto v: g[u]){
            if(!visited[i][v] and d+1 < dis[i][v]){
                dis[i][v] = d + 1;
                pq.push({d+1, v});
            }
        }
    }
}

int tree(int u, int v, int mod){
    u = u % mod;
    v = v % mod;
    if(level[v] < level[u]) swap(u, v); // level[u] < level[v]
    int cnt = 0;
    while(level[v] != level[u]){
        cnt ++;
        v = v/2;
    }
    while(u != v){
        u = u/2;
        v = v/2;
        cnt += 2;
    }
    return cnt;
}

int main(){

    int k, l, Q;
    scanf("%d%d%d", &k, &l, &Q);

    N = 1 << (k+1);

    setting(k);

    for(int i=0;i<l;i++){
        int a, b;
        scanf("%d%d", &a, &b);
        g[a].push_back(b);
        g[b].push_back(a);
        imp.push_back(a);
        imp.push_back(b);
    }

    /*for(int u = 1; u <= N; u++){
        printf("%d : ", u);
        for(auto v: g[u]) printf("%d ", v);
        printf("\n");
    }*/

    for(int i=0;i<2*l;i++){
        distance(i);
        /*for(int j=1;j<=N;j++){
            printf("%d ", dis[i][j]);
        }
        printf("\n");*/
    }

    while(Q--){
        int x, y;
        scanf("%d%d", &x, &y);
        int ans = INF;
        if((x < (1<<k) and y < (1 << k)) or (x > (1<<k) and y > (1<<k))) ans = tree(x, y, 1<<k);
        for(int i=0;i<2*l;i++){
            ans = min(ans, dis[i][x] + dis[i][y]);
        }
        printf("%d\n", ans);
    }

    return 0;
}