题解 | 复合共轭图构造

def solve(testcase):
    n, m1, m2 = MI()
    edges = []

    for _ in range(m1):
        u, v = GMI()
        edges.append((u, v))
    
    ufG = UnionFind(n)

    for _ in range(m2):
        u, v = GMI()
        ufG.Union(u, v)
    
    res = 0
    ufF = UnionFind(n)

    for u, v in edges:
        if ufG.connected(u, v):
            ufF.Union(u, v)
        else:
            res += 1
    
    mp = ufG.all_group_members()

    for rt in mp:
        nodes = mp[rt]
        m = len(nodes)
        u = nodes[0]

        for i in range(1, m):
            v = nodes[i]
            res += ufF.Union(u, v)
    
    print(res)

for testcase in range(II()):
    solve(testcase)