for each test case:
  read W, E, C
  read western connections
  read eastern connections
  initialize graph with W+E-2 nodes
  initialize distance matrix with INF
  for each western connection:
    connect western stations in the graph
    set distance[i][j] = 1 for connected stations
  for each eastern connection:
    connect eastern stations in the graph
    set distance[i][j] = 1 for connected stations
  for i = 1 to C:
    read A, B
    connect A-th western station to B-th eastern station
    connect B-th eastern station to A-th western station
    set distance[A][B] = set distance[B][A] = 1
    run Floyd-Warshall algorithm to calculate all pairs shortest path
    calculate average distance of the resulting map
    output the result