metronibus

#include<bits/stdc++.h>
#define pii pair<int,int>
#define MAXN 100010

using namespace std;

const int INF = 0x3f3f3f3f;

vector<pii> grafo[2*MAXN];

deque<pii> dq;
int dist[2*MAXN];

void bfs01(int s){
    dq.push_front({s, 0});
    dist[s] = 0;

    while(!dq.empty()){
        pii v = dq.front();
        dq.pop_front();
        for(auto e : grafo[v.first]){
            int viz = e.first;
            int w = e.second;
            if(dist[v.first]+w < dist[viz]){
                dist[viz] = dist[v.first]+w;
                if(w == 1){
                    dq.push_back(e);
                }
                else{
                    dq.push_front(e);
                }
            }
        }
    }
}

int main(){
    int n, k1, k2, p;
    scanf("%d %d %d %d", &n, &k1, &k2, &p);

    for(int i = 0; i < k1; i++){
        int a, b; scanf("%d %d", &a, &b);
        grafo[2*a-1].push_back({2*b-1, 0});
        grafo[2*b-1].push_back({2*a-1, 0});
    }

    for(int i = 0; i < k2; i++){
        int a, b; scanf("%d %d", &a, &b);
        grafo[2*a].push_back({2*b, 0});
        grafo[2*b].push_back({2*a, 0});
    }

    int ini, fim; scanf("%d %d", &ini, &fim);

    for(int i = 1; i <= 2*n; i+=2){
        if(grafo[i].size() != 0 && grafo[i+1].size() != 0){
            grafo[i].push_back({i+1, 1});
            grafo[i+1].push_back({i, 1});
        }
    }

    int resp1=INF, resp2=INF, resp;
    if(grafo[ini*2-1].size() != 0){
        memset(dist, INF, sizeof dist);
        bfs01(ini*2-1);
        resp1 = min(dist[fim*2-1], dist[fim*2]);
    }
    if(grafo[ini*2].size() != 0){
        memset(dist, INF, sizeof dist);
        bfs01(ini*2);
        resp2 = min(dist[fim*2-1], dist[fim*2]);
    }

    resp = min(resp1, resp2);

    if(resp == INF){
        printf("-1");
        return 0;
    }

    printf("%d", (resp+1)*p);
}