P1004

#include <bits/stdc++.h>

const int N = 5010;
int n, m, q;
int head[N], nxt[N << 1], to[N << 1], idx;
std::queue<int> que, queano;
bool vis[N], visano[N];
std::vector<int> ddd[N];
int dep[N], depano[N];
int func[N][N];


void add(int u, int v) {
    nxt[idx] = head[u];
    to[idx] = v;
    head[u] = idx;
    ++ idx;
    return;
}
void dist(int x, std::vector<int> &dis) {
    dis.resize(n + 1);
    dis[x] = 0;
    vis[x] = true;
    que.push(x);
    while (!que.empty()) {
        int t = que.front();
        que.pop();
        for (int i = head[t]; i != -1; i = nxt[i]) {
            int e = to[i];
            if (!vis[e]) {
                vis[e] = true;
                dis[e] = dis[t] + 1;
                que.push(e);
            }
        }
    }
    for (int i = 1; i <= n; ++ i) {
        vis[i] = false;
    }
    return;
}
void bfsearch(int x, int z) {
    dep[x] = 0;
    vis[x] = true;
    que.push(x);
    while (!que.empty()) {
        int t = que.front();
        que.pop();
        for (int i = head[t]; i != -1; i = nxt[i]) {
            int e = to[i];
            if (!vis[e] && ddd[z][e] + dep[t] + 1 == ddd[z][x]) {
                vis[e] = true;
                dep[e] = dep[t] + 1;
                que.push(e);
            }
        }
        depano[x] = 0;
        queano.push(t);
        while (!queano.empty()) {
            int tano = queano.front();
            queano.pop();
            for (int i = head[tano]; i != -1; i = nxt[i]) {
                int eano = to[i];
                if (!depano[eano] && ddd[z][eano] == ddd[z][t] + depano[tano] + 1) {
                    depano[eano] = depano[tano] + 1;
                    queano.push(eano);
                    func[x][eano] = std::min(func[x][eano], ddd[z][x] + depano[eano]);
                }
            }
        }
    }
    for (int i = 1; i <= n; ++ i) {
        vis[i] = visano[i] = false;
        depano[i] = 0;
    }
    return;
}

int main(void) {
    memset(head, -1, sizeof(head));

    int inpu, inpv, inpo, inpa, inpb, inpc;
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= m; ++ i) {
        scanf("%d%d", &inpu, &inpv);
        add(inpu, inpv);
        add(inpv, inpu);
    }
    for (int i = 1; i <= n; ++ i) {
        dist(i, ddd[i]);
    }

    for (int i = 1; i <= q; ++ i) {
        scanf("%d", &inpo);
        if (inpo == 1) {
            scanf("%d%d", &inpu, &inpv);
            printf("%d\n", ddd[inpu][inpv]);
        } else if (inpo == 2) {
            scanf("%d%d%d", &inpa, &inpb, &inpc);
            for (int j = 1; j <= n; ++ j) {
                for (int k = 1; k <= n; ++ k) {
                    func[j][k] = 0x3f3f3f3f;
                }
                func[j][j] = ddd[inpc][j];
            }
            for (int j = 1; j <= n; ++ j) {
                bfsearch(j, inpc);
            }
            int ans = 0x3f3f3f3f;
            for (int j = 1; j <= n; ++ j) {
                if (ddd[inpa][j] + ddd[j][inpc] != ddd[inpa][inpc]) {
                    continue;
                }
                for (int k = 1; k <= n; ++ k) {
                    if (ddd[inpa][j] + ddd[j][k] + ddd[k][inpb] != ddd[inpa][inpb]) {
                        continue;
                    }
                    if (ddd[inpb][k] + ddd[k][inpc] != ddd[inpb][inpc]) {
                        continue;
                    }
                    ans = std::min(ans, ddd[inpa][inpb] + func[j][k]);
                }
            }
            printf("%d\n", ans);
        }
    }


    return 0;
}