def disjoint_union(*graphs):
    """Given a list of graphs, construct their disjoint union."""
    res_vertices = []
    res_edges = []
    for (vertices, edges) in graphs:
        l = len(res_vertices)
        res_edges.extend((a+l, b+l) for (a, b) in edges)
        res_vertices.extend(vertices)
    return (res_vertices, res_edges)