from collections import deque

def calculate_shortest_paths(western_connections, eastern_connections, w, e):
    western_distances = [-1] * w
    eastern_distances = [-1] * e
    for i in range(w):
        if western_distances[i] != -1:
            continue
        q = deque()
        q.append(i)
        western_distances[i] = 0
        while len(q) > 0:
            u = q.popleft()
            for v in western_connections[u]:
                if western_distances[v] == -1:
                    western_distances[v] = western_distances[u] + 1
                    q.append(v)
    for i in range(e):
        if eastern_distances[i] != -1:
            continue
        q = deque()
        q.append(i)
        eastern_distances[i] = 0
        while len(q) > 0:
            u = q.popleft()
            for v in eastern_connections[u]:
                if eastern_distances[v] == -1:
                    eastern_distances[v] = eastern_distances[u] + 1
                    q.append(v)
    return western_distances, eastern_distances

def calculate_average_distance(western_connections, eastern_connections, w, e, options):
    western_distances, eastern_distances = calculate_shortest_paths(western_connections, eastern_connections, w, e)
    total_distance = sum(western_distances) * e + sum(eastern_distances) * w
    for option in options:
        a, b = option
        a -= 1
        b -= 1
        dist = western_distances[a] + eastern_distances[b] + 1
        total_distance += (dist - min(western_distances[a] + eastern_distances[b], western_distances[b] + eastern_distances[a])) * 2
        western_connections[a].append(b + w)
        western_connections[b].append(a + w)
        eastern_connections[b].append(a + w)
        eastern_connections[a].append(b + w)
        w_e_connections = []
        for i in range(w):
            w_e_connections.append([])
        for i in range(e):
            w_e_connections.append([])
        for i in range(w):
            for j in western_connections[i]:
                w_e_connections[i].