from heapq import heappush, heappop

INF = int(1e9)

def dijkstra(adj, start):
    n = len(adj)
    dist = [INF] * n
    dist[start] = 0
    pq = [(0, start)]
    
    while pq:
        d, u = heappop(pq)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heappush(pq, (dist[v], v))
    
    return dist

def solve():
    w, e, c = map(int, input().split())
    w_adj = [[] for _ in range(w)]
    e_adj = [[] for _ in range(e)]
    
    # read in existing connections
    for i, x in enumerate(map(int, input().split()), start=1):
        w_adj[i-1].append((x-1, 1))
        w_adj[x-1].append((i-1, 1))
    for j, f in enumerate(map(int, input().split()), start=1):
        e_adj[j-1].append((f-1, 1))
        e_adj[f-1].append((j-1, 1))
        
    # precompute shortest paths between western and eastern stations
    dist = [[0] * e for _ in range(w)]
    for i in range(w):
        dist[i] = dijkstra(e_adj, i)
        
    # calculate new shortest paths for each option for an overpass connection
    results = []
    for _ in range(c):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        
        # dynamic programming to calculate new shortest paths
        new_dist = [[INF] * (w+e) for _ in range(w+e)]
        for i in range(w):
            for j in range(e):
                new_dist[i][j+w] = new_dist[j+w][i] = dist[i][j] + 2
                
        for i, (u, v) in enumerate(w_adj):
            for j, (x, y) in enumerate(e_adj):
                new_dist[u][x+w] = new_dist[x+w][u] = min(new_dist[u][x+w], dist[i][j]+2+y)
                new_dist[v][x+w] = new_dist[x+w][v] = min(new_dist[v][