There are N cities numbered 1 through N, and M bidirectional roads numbered 1 through M. Road i connects City A_i and City B_i.  Snuke can perform the following operation zero or more times:    * Choose two distinct cities that are not directly connected by a road, and build a new road between the two cities.  After he finishes the operations, it must be possible to travel from any city to any other cities by following roads (possibly multiple times).  What is the minimum number of roads he must build to achieve the goal?
def main():
    n, m = map(int, input().split())
    g = [-1]*(n+1)
    gidx = 0
    group = [-1]*(n+1)
    idx = 0
    for i in range(m):
        a, b = map(int, input().split())
        ak,bk = group[a], group[b]
        if ak>=0 and bk>=0:
            if ak != bk:
                g[bk] = g[ak]
        elif ak<0 and bk>=0:
            group[a] = bk
        elif ak>=0 and bk<0:
            group[b] = ak
        else:
            group[a] = group[b] = idx
            idx += 1
            g[idx] = gidx
            gidx += 1

    print(g)
    print(group)
    
    
    ans = len(set(g))-1
    
    ans += len([v for v in group[1:] if v==-1])-1
    print(ans)

main()
def main():
    n, m = map(int, input().split())
    
    uf = [-1] * (n+1)

    def uf_leader(a):
        if uf[a]<0:
            return a
        uf[a] = uf_leader(uf[a])
        return uf[a]
    def uf_unite(a, b):
        ua, ub = uf_leader(a), uf_leader(b)
        if ua==ub:
            return False
        if uf[ua] > uf[ub]:
            ua, ub = ub, ua
        uf[ua] += uf[ub]
        uf[ub] = ua
        return True
    def uf_leaders():
        return [v for v in range(1,n+1) if uf[v]<0]

    
    for _ in range(m):
        a, b = map(int, input().split())
        uf_unite(a, b)
        

    
    
    ans = len(uf_leaders())-1
    print(ans)

main()
