Problem:
 Score : 300 points    Problem Statement 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?      Constraints  2 \leq N \leq 100,000  1 \leq M \leq 100,000  1 \leq A_i < B_i \leq N  No two roads connect the same pair of cities.  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  M  A_1  B_1  :  A_M  B_M       Output Print the answer.        Sample Input 1 3 1
1 2      Sample Output 1 1  Initially, there are three cities, and there is a road between City 1 and City 2 .  Snuke can achieve the goal by building one new road, for example, between City 1 and City 3 .
After that,   We can travel between 1 and 2 directly.  We can travel between 1 and 3 directly.  We can travel between 2 and 3 by following both roads ( 2 - 1 - 3 ).

Solution (Python):
n,m=map(int,input().split())


class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x == y:
      return False

    if self.parents[x] > self.parents[y]:
      x, y = y, x
    self.parents[x] += self.parents[y]
    self.parents[y] = x
    return True

  def size(self, x):
    return -self.parents[self.find(x)]

  def same(self, x, y):
    return self.find(x) == self.find(y)

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

  def group_count(self):
    return len(self.roots())

  def all_group_members(self):
    return {r: self.members(r) for r in self.roots()}

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

uf = UnionFind(n)
for i in range(m):
  x,y=map(int,input().split())
  uf.union(x-1,y-1)
print(uf.group_count()-1)

Solution (Python):
from collections import deque

n, m = map(int, input().split())
road = [[] for _ in range(n)]
flag = [-1 for _ in range(n)]

for i in range(m):
  a, b = map(int, input().split())
  road[a-1].append(b-1)
  road[b-1].append(a-1)

count = 0

for k in range(n):
  if(flag[k] != -1):
    continue
  
  count += 1
  queue = deque([k])
  while queue:
    now = queue.popleft()
    flag[now] = count
    for i in road[now]:
      if(flag[i] == -1):
        queue.append(i)
  
print(count-1)

Solution (Python):
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush

sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m = inpm()
AB = inplt(m)

uf = UnionFind(n)
for a,b in AB:
    uf.union(a-1,b-1)

print(uf.group_count()-1)

Solution (Python):
class uft():
    def __init__(self,n):
        
        self.p=[ -1 for i in range(n)]
        
        self.r=[ 1 for i in range(n)]
        
        self.e=[ 1 for i in range(n)]
        
    def find(self,x):
        if(self.p[x]==-1):
            return x
        else:
            self.p[x]=self.find(self.p[x])
            return self.find(self.p[x])
        
    def unite(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if(x==y):
            return
        
        if(self.r[x]>self.r[y]):
            tmp=x
            x=y
            y=tmp
        
        if(self.r[x]==self.r[y]):
            self.r[y]+=1
        
        self.e[y]+=self.e[x]
            
        if(x!=y):
            self.p[x]=y
        return
    
    def tsize(self,x):
        return self.e[self.find(x)]
n,m=map(int,input().split())

uf=uft(n)
for i in range(m):
    x,y=map(int,input().split())
    x-=1
    y-=1
    uf.unite(x,y)
oya=0

for i in range(n):
    if(uf.p[i]==-1):
        oya+=1
print(oya-1)

Solution (Python):
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext

def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

class UnionFind:
    
    
    def __init__(self, n):
        self.n = n
        
        
        self.root = [-1]*(n+1)
        
        self.rank = [0]*(n+1)

    
    def findRoot(self, x):
        if(self.root[x] < 0): 
            return x
        else:
            
            self.root[x] = self.findRoot(self.root[x])
            return self.root[x]

    
    def unite(self, x, y):
        
        x = self.findRoot(x)
        y = self.findRoot(y)

        
        if x == y:
            return 

        
        if self.rank[x] > self.rank[y]:
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    
    def isSameGroup(self, x, y):
        return self.findRoot(x) == self.findRoot(y)

    
    def count(self, x):
        return -self.root[self.findRoot(x)]

def main():
    n, m = i_map()

    uf = UnionFind(n)

    for _ in range(m):
        a, b = i_map()
        uf.unite(a, b)

    count = 0
    for i in range(2, n+1):
        if uf.isSameGroup(1, i):
            continue
        uf.unite(1, i)
        count += 1

    print(count)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
N,M=map(int, sys.stdin.readline().split())

par=[ i for i in range(N+1) ]
size=[ 1 for i in range(N+1) ]


def root(x):
    while par[x]!=x:
        x=par[x]
    return x

def same(x,y):
	return root(x)==root(y)

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y: return
    if size[y]<size[x]: x,y=y,x
    size[y]+=size[x]
    par[x]=y

def getsize(x):
	return size[root(x)]

for _ in range(M):
    a,b=map(int, sys.stdin.readline().split())
    unite(a,b)

s=set()
for i in range(1,N+1):
    s.add(root(i))

print len(s)-1

Solution (Python):
from collections import deque
def bfs(edges,start):
    waiting = deque()
    done[start] = 2
    c = 1
    for n in edges[start]:
        done[n] = 1
        waiting.append(n)
    while len(waiting):
        cur_node = waiting.popleft()
        if done[cur_node] != 2:
            done[cur_node] = 2
            c += 1
            for n in edges[cur_node]:
                if done[n] != 2:
                    done[n] = 1
                    waiting.append(n)
    
    return c 
N,M = [int(a) for a in input().split()]
edge = [[] for _ in range(N)] 
for _ in range(M):
    a,b = [int(a) for a in input().split()]
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
done = [0]*N
ans = []
for i in range(N):
    if done[i]==0: ans.append(bfs(edge,i))

print(len(ans)-1)

Solution (Python):
n, m = map(int, input().split())

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

uf = UnionFind(n+1)
A = [0]*m
B = [0]*m
for i in range(m):
    A[i], B[i] = sorted(map(int, input().split()))
    uf.union(A[i], B[i])
print(uf.group_count()-2)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def inp():
    return int(input())
def inps():
    return input().rstrip()
def inpl():
    return list(map(int, input().split()))
def inpls():
    return list(map(str, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)













class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N, M = inpl()
graph = [[] for i in range(N + 1)]
uf = UnionFind(N + 1)

for i in range(M):
    a, b = inpl()
    uf.union(a, b)

print(len(uf.roots()) - 2)

Solution (Python):









import os
import sys
sys.setrecursionlimit(2000000)




def BFS(cnt, color, path, u):
    color[u] = cnt
    for v in path[u]:
        if color[v] == -1:
            BFS(cnt, color, path, v)


def main():
    N, M = map(int, input().split())
    path = [[] for _ in range(N+1)]
    for _ in range(M):
        A, B = map(int, input().split())
        path[A].append(B)
        path[B].append(A)
    color = [-1] * (N+1)
    cnt = 0
    for i in range(1, N+1):
        if color[i] == -1:
            BFS(cnt, color, path, i)
            cnt += 1
    print(max(color))


if __name__ == "__main__":
    main()

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m = map(int,input().split())
uf = UnionFind(n)
for _ in range(m):
  a,b = map(int,input().split())
  uf.union(a-1,b-1)
root = [0]*n
for i in range(n):
  root[uf.find(i)] += 1
cnt = 0
for v in root:
  if v!=0:
    cnt += 1
print(cnt-1)

Solution (Python):
import collections

n, m = map(int, input().split())

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
                
UF = UnionFind(n)

for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    
    UF.union(a, b)

for i in range(n):
    _ = UF.find(i)

c = collections.Counter(UF.par)
print(len(c.keys()) - 1)

Solution (Python):

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())


def main():
    N, M = map(int, input().split())

    uf = UnionFind(N)

    for m in range(M):
        A, B = map(int, input().split())
        A, B = A-1, B-1
        uf.union(A, B)
    
    print(uf.group_count() - 1)


if __name__ == '__main__':
    main()

Solution (Python):



import queue 
import bisect



    






mod = int(1e9+7)

INF = 1<<50

def readInt():
    return list(map(int,input().split()))

def main():
    n,m = readInt()
    road = [[] for i in range(n)]
    for i in range(m):
        a,b = readInt()
        road[a-1].append(b-1)
        road[b-1].append(a-1)
    ans = 0
    city = set(i for i in range(n))
    while len(city):
        q = queue.Queue()
        q.put(city.pop())
        visit = set()
        while not q.empty():
            x = q.get()
            visit.add(x)
            for i in road[x]:
                if i not in visit:
                    q.put(i)
                    city.discard(i)
        if len(city):
            ans += 1
    print(ans)
    return

if __name__=='__main__':
    main()

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x) ; y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)
    
N,M=map(int,input().split())
uf=UnionFind(N)
for i in range(M):
    a,b=map(int,input().split(' '))
    uf.union(a-1,b-1)

ans=sum([1 for i in uf.parents if i<0])-1
print(ans)

Solution (Python):

N,M = map(int, input().split())
A = [-1 for i in range(M)]
B = [-1 for i in range(M)]
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

for i in range(M):
    A[i],B[i] = map(int, input().split())

uf = UnionFind(N)

for i in range(M):
    uf.union(A[i]-1,B[i]-1)

print(uf.group_count()-1)

Solution (Python):
n,m = map(int,input().split())

class UnionFindVerSize():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        
        self._parent = [n for n in range(0, N)]
        
        self._size = [1] * N

    def find_root(self, x):
        """ xの木の根(xがどのグループか)を求める """
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x]) 
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属するグループを併合する """
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        """ xが属するグループのサイズ（個数）を返す """
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        """ グループ数を計算して返す """
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans
      
uf = UnionFindVerSize(n)

for _ in range(m):
  a,b = map(int,input().split())
  uf.unite(a-1,b-1)

a = uf.calc_group_num()
print(a-1)

Solution (Python):
from sys import setrecursionlimit

class UnionFind:
    def __init__(self, n):
        self._n = n
        self.parent_or_size = [-1] * n

    def union(self, a, b):
        assert 0 <= a < self._n
        assert 0 <= b < self._n
        x, y = self.find(a), self.find(b)
        if x == y: return x
        if -self.parent_or_size[x] < -self.parent_or_size[y]: x, y = y, x
        self.parent_or_size[x] += self.parent_or_size[y]
        self.parent_or_size[y] = x
        return x

    def same(self, a, b):
        assert 0 <= a < self._n
        assert 0 <= b < self._n
        return self.find(a) == self.find(b)

    def find(self, a):
        assert 0 <= a < self._n
        if self.parent_or_size[a] < 0: return a
        self.parent_or_size[a] = self.find(self.parent_or_size[a])
        return self.parent_or_size[a]

    def size(self, a):
        assert 0 <= a < self._n
        return -self.parent_or_size[self.find(a)]

    def groups(self):
        find_buf = [self.find(i) for i in range(self._n)]
        result = [[] for _ in range(self._n)]
        for i in range(self._n): result[find_buf[i]].append(i)
        return [r for r in result if r != []]

N, M = map(int,input().split())
uf = UnionFind(N)
setrecursionlimit(10**9+7)

for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    uf.union(a,b)

print(len(uf.groups())-1)

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]

uf = UnionFind(N)
for a,b in AB:
    uf.union(a-1,b-1)

print(uf.group_count() - 1)

Solution (Python):

import sys
input = sys.stdin.readline


from bisect import bisect_left;
from bisect import bisect_right;
from math import ceil, factorial;

def ceil(x):
    if x != int(x):
        x = int(x) + 1;
    return x;
    

def swaparr(arr, a,b):
    temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;


def gcd(a,b):
    if b == 0:
        return a;
    return gcd(b, a % b);


def nCr(n, k, modulus = 1): 
    if(k > n - k): 
        k = n - k; 
    res = 1;
    for i in range(k): 
        res = res * (n - i);
        res = res / (i + 1);
        res %= modulus; 
    return int(res);


def primefs(n):
    
    primes = {}
    while(n%2 == 0 and n > 0):
        primes[2] = primes.get(2, 0) + 1
        n = n//2
    for i in range(3, int(n**0.5)+2, 2):
        while(n%i == 0 and n > 0):
            primes[i] = primes.get(i, 0) + 1
            n = n//i
    if n > 2:
        primes[n] = primes.get(n, 0) + 1
    
    
    return primes


def power(x, y, p): 
    res = 1
    x = x % p  
    if (x == 0) : 
        return 0
    while (y > 0) : 
        if ((y & 1) == 1) : 
            res = (res * x) % p 
        y = y >> 1      
        x = (x * x) % p 
    return res 


def swap(a,b):
    temp = a
    a = b
    b = temp
    return a,b;









def find(x, link):
    p = x;
    while( p != link[p]):
        p = link[p];
    
    while( x != p):
        nex = link[x];
        link[x] = p;
        x = nex;
    return p;




def union(x, y, link, size):
    x = find(x, link)
    y = find(y, link)
    if size[x] < size[y]:
        x,y = swap(x,y)
    if x != y:
        size[x] += size[y]
        link[y] = x


def sieve(n): 
    prime = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
        if (prime[p] == True): 
            for i in range(p * p, n+1, p):
                prime[i] = False
        p += 1
    return prime


MAXN = int(1e6 + 5)
def spf_sieve():
    spf[1] = 1;
    for i in range(2, MAXN):
        spf[i] = i;
    for i in range(4, MAXN, 2):
        spf[i] = 2;
    for i in range(3, ceil(MAXN ** 0.5), 2):
        if spf[i] == i:
            for j in range(i*i, MAXN, i):
                if spf[j] == j:
                    spf[j] = i;
    




def factoriazation(x):
    ret = {};
    while x != 1:
        ret[spf[x]] = ret.get(spf[x], 0) + 1;
        x = x//spf[x]
    return ret;
    
    


def int_array():
    return list(map(int, input().strip().split()));

def float_array():
    return list(map(float, input().strip().split()));


def str_array():
    return input().strip().split();


MOD = int(1e9)+7;
CMOD = 998244353;
INF = float('inf'); NINF = -float('inf');



n, m = int_array();
link = [i for i in range(n + 1)];
size = [1 for i in range(n + 1)];
for _ in range(m):
    a, b = int_array();
    union(a, b, link, size);
ans = set();
for i in range(1, len(link)):
    ans.add(find(link[i], link));
print(len(ans) - 1);

Solution (Python):
N, M = map(int, input().split())
ab = [0] * M
for i in range(M):
    ab[i] = list(map(int, input().split()))

import sys
sys.setrecursionlimit(100500)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

uf = UnionFind(N)

for i in range(M):
    uf.union(ab[i][0]-1, ab[i][1]-1)

print(uf.group_count() - 1)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n, m = map(int, input().split())
graph = [0] + [[] for _ in range(n)]
for _ in range(m):
    n1, n2 = map(int, input().split())
    graph[n1].append(n2)
    graph[n2].append(n1)

from collections import deque

def bfs(graph, queue, dist):
    while queue:
        current = queue.popleft()

        for _next in graph[current]:
            if dist[_next] != -1:
                continue
            else:
                dist[_next] = dist[current] + 1
                queue.append(_next)

dist = [0] + [-1] * n
part = 0
for i in range(1, n + 1):
    if dist[i] != -1:
        continue
    else:
        queue = deque([i])
        dist[i] = 0
        bfs(graph, queue, dist)
        part += 1
print(part - 1)

Solution (Python):
import math



class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, v):  
        if self.parents[v] < 0:
            return v
        else:
            self.parents[v] = self.find(self.parents[v])
            return self.parents[v]

    def unite(self, u, v):  
        u = self.find(u)
        v = self.find(v)
        if u == v:
            return
        if self.parents[u] > self.parents[v]:  
            u, v = v, u
        self.parents[u] += self.parents[v]
        self.parents[v] = u

    def size(self, v):  
        return -self.parents[self.find(v)]

    def same(self, u, v):  
        return self.find(u) == self.find(v)






def comb(n, r):  
    if r < 0 or r > n:
        return 0
    else:
        n1 = math.factorial(n)
        n21 = math.factorial(n - r)
        n22 = math.factorial(r)
        ans = n1 // (n21 * n22)
        return ans


N, M = map(int, input().split())
uf = UnionFind(N)

for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    uf.unite(a, b)

root_list = []
for i in range(N):
    r = uf.find(i)
    root_list.append(r)

root_list = list(set(root_list))
num = len(root_list)

ans = num - 1
print(ans)

Solution (Python):





class UnionFind():
    """
    下記から拝借
    https://note.nkmk.me/python-union-find/
    """

    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join(
            '{}: {}'.format(r, self.members(r)) for r in self.roots())






def solve(N, M, AB):
    nf = UnionFind(N)
    for a, b in AB:
        nf.union(a - 1, b - 1)
    print(nf.group_count() - 1)


if __name__ == '__main__':
    
    
    N, M = map(int, input().split())
    
    
    AB = [[int(i) for i in input().split()] for _ in range(M)]
    solve(N, M, AB)