from heapq import heappush, heappop

def dijkstra(graph, start):
    dist = {v: float('inf') for v in graph}
    dist[start] = 0
    heap = [(0, start)]
    while heap:
        d, u = heappop(heap)
        if d > dist[u]:
            continue
        for v, weight in graph[u]:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                heappush(heap, (dist[v], v))
    return dist

def solve_case(w, e, c, w_connections, e_connections, overpass_connections):
    # Build graph without overpass connections
    graph = {i: [] for i in range(1, w+e)}
    for i in range(w-1):
        u, v = i+1, w_connections[i]
        graph[u].append((v, 1))
        graph[v].append((u, 1))
    for i in range(e-1):
        u, v = i+1+w, e_connections[i]+w
        graph[u].append((