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):
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())
        
a = input().split()
N = int(a[0])
M = int(a[1])
tm = int(0)
tmp = int(0)


k = [input().split() for i in range(M)]

uf = UnionFind(N+1)

for i in range(M):
    tm = int(k[i][0])
    tmp = int(k[i][1])
    uf.union(tm, tmp)
    tm = 0
    tmp = 0

print(int(uf.group_count()) - 2)

Solution (Python):

import sys
import networkx as nx

def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    G = nx.Graph()

    for i in range(1, N+1):
        G.add_node(i)

    for i in range(M):
        G.add_edge(A[i], B[i])

    if nx.is_connected(G):
        print(0)
    else:
        print(nx.number_connected_components(G)-1)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    A = [int()] * (M)  
    B = [int()] * (M)  
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()

Solution (Python):

from math import floor, ceil, sqrt, factorial, log, gcd, log10
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement, chain
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop, heapify
from copy import copy, deepcopy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))




def I(): return int(sys.stdin.buffer.readline())



def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()




def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')



def IR(n): return [I() for i in range(n)]






def LIR(n): return [LI() for i in range(n)]






def SR(n): return [S() for i in range(n)]






def LSR(n): return [LS() for i in range(n)]






def SRL(n): return [list(S()) for i 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 = LI()
uf = UnionFind(n)
for _ in range(m):
    a, b = LI()
    uf.union(a-1, b-1)
print(uf.group_count()-1)

Solution (Python):
N, M = map(int, input().split())
cla = [i for i in range(N)]
count = set()
def root(a):
    change = []
    while cla[a] != a:
        change.append(a)
        a = cla[a]
    for i in change:
        cla[i] = a
    return a
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if root(a) != root(b):
        cla[root(b)] = root(a)
for i in range(N):
    count |= {root(i)}
print(len(count) - 1)

Solution (Python):
import numpy as np
import sys
sys.setrecursionlimit(10 ** 7)

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

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

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

		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 size(self, x):
		return abs(self.parents[self.find(x)])
      
      
uf=UnionFind(N)
for i in range(M):
  A,B=map(int,input().split())
  uf.union(A-1,B-1)
  
print(len(uf.parents[uf.parents<0])-1)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.UF = [i for i in range(n)]
    def union(self,x,y):
        px = self.find(x)
        py = self.find(y)
        self.UF[px] = py
    def find(self, x):
        if self.UF[x] == x:
            return x
        self.UF[x] = self.find(self.UF[x])
        return self.UF[x]
 
n,m = [int(x) for x in input().split()]
UF = UnionFind(n)
for _ in range(m):
    a,b = [int(x) for x in input().split()]
    a -= 1
    b -= 1
    UF.union(a,b)
 
ANS = []
for i in range(n):
    if UF.find(i) != UF.find(0):
        ANS.append((0,i))
        UF.union(i, 0)
print(len(ANS))

Solution (Python):
n, m = map(int, input().split(' '))
cnt = 0
circles = [x for x in range(n)]

def find(x):
  if circles[x] == x:
    return x
  root = find(circles[x])
  circles[x] = root
  return root

for _ in range(m):
  a, b = map(int, input().split(' '))
  if find(a - 1) != find(b - 1):
    circles[find(a - 1)] = find(b - 1)
    
print(sum(1 for i, j in enumerate(circles) if i == j) - 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())
uf=UnionFind(n)
for i in range(m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  uf.union(a,b)
print(uf.group_count()-1)

Solution (Python):
class Tree:
    def __init__(self, N):
        self.N = N
        self.nodes = [ Node(i) for i in range(N) ]

    def get_root(self, node):
        if node.parent is None:
            return node
        root = self.get_root(node.parent)
        node.parent = root
        return root

    def merge(self, node1, node2):
        root1 = self.get_root(node1)
        root2 = self.get_root(node2)

        if root1.ID == root2.ID:
            return

        root1.parent = root2

    def get_root_count(self):
        count = 0
        for n in self.nodes:
            if n.parent is None:
                count += 1
        return count

class Node:
    def __init__(self, ID):
        self.ID = ID
        self.parent = None

def main():
    N, M = map(int, input().split())
    tree = Tree(N)
    for i in range(M):
        A, B = map(int, input().split())
        A, B = A-1, B-1
        tree.merge(tree.nodes[A], tree.nodes[B])
    print(tree.get_root_count() - 1)


main()

Solution (Python):

class UnionFind:
    def __init__(self, N):
        self.root = list(range(N + 1))
        self.size = [1] * (N + 1)

    def __getitem__(self, x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    def merge(self, x, y):
        x = self[x]
        y = self[y]
        if x == y:
            return
        sx, sy = self.size[x], self.size[y]
        if sx < sy:
            x, y = y, x
            sx, sy = sy, sx
        self.root[y] = x
        self.size[x] += sy

    def same(self,x,y):
        return  self[x] == self[y]

    def find_max(self):
        return max(self.size)

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

uf = UnionFind(N)
merge = uf.merge
same = uf.same

for i in range(M):
    a,b = map(int, input().split())
    merge(a,b)
count = -1
for ind,j in enumerate(uf.root):
    if ind == j:
        count += 1

print(count -1)

Solution (Python):
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)]

n,m = map(int,input().split())
t = UnionFind(n)
for _ in range(m):
    a,b = map(int,input().split())
    t.unite(a,b)


print(len([a for a in t.root[1::] if a < 0])-1)

Solution (Python):
import math

class UnionFind:
    def __init__(self, size):
        self.parent_indexes = [-1] * size
        
    def find(self, n):
        if self.parent_indexes[n] < 0:
            return n
        
        
        self.parent_indexes[n] = self.find(self.parent_indexes[n])
        return self.parent_indexes[n] 
    
    def union(self, n1, n2):
        if self.same_group(n1, n2):
            return False
        
        
        if self.size(n1) >= self.size(n2):
            tmp = self.size(n2)
            self.parent_indexes[self.find(n2)] = self.find(n1)
            self.parent_indexes[self.find(n1)] -= tmp
            return True
        
        
        tmp = self.size(n1)
        self.parent_indexes[self.find(n1)] = self.find(n2)
        self.parent_indexes[self.find(n2)] -= tmp
        return True
        
    
    def size(self, n):
        return -self.parent_indexes[self.find(n)]
    
    def same_group(self, n1, n2):
        return self.find(n1) == self.find(n2)

n, m = map(lambda x: int(x), input().split())


uf = UnionFind(n)

for _ in range(m):
    a, b = map(lambda x: int(x), input().split())
    uf.union(a-1, b-1)
    
num_parents = 0
    
for p_index in uf.parent_indexes:
    if p_index < 0:
        num_parents += 1

print(num_parents - 1)

Solution (Python):


import sys
sys.setrecursionlimit(10**9)


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1 for _ in range(n)]

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

    def union(self, n, m):
        x = self.find(n)
        y = self.find(m)
        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


n, m = map(int, input().split())
U = UnionFind(n)
for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    U.union(a, b)

P = U.parents
ans = 0
for p in P:
    if p < 0:
        ans += 1
print(ans-1)

Solution (Python):
def ConectCities():
    from collections import deque
    n, m = map(int, input().split())
    a = [[] for _ in range(n)]
    route = set()
    ans = 0
    q = deque()

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

    for i in range(n):
        if i in route:
            continue
        elif i != 0:
            ans += 1
        route.add(i)
        q.append(i)
        
        while q:
            k = q.pop()
            route.add(k)
            for j in a[k]:
                if j in route:
                    continue
                route.add(j)
                q.append(j)
        if len(route) == n:
            print(ans)
            break

if __name__ == '__main__':
    ConectCities()

Solution (Python):
import sys
sys.setrecursionlimit(100002)

input = lambda : sys.stdin.readline().rstrip()


def main(a_s, b_s, n, m):
    graph = {}
    for node in range(1, n+1):
        graph[node] = []

    for i in range(m):
        a, b = a_s[i], b_s[i]
        graph[a].append(b)
        graph[b].append(a)

    uses = [False] * (n+1)

    def check(node):
        uses[node] = True
        kids = graph[node]
        for kid in kids:
            if not uses[kid]:
                check(kid)

    next_graph_i = 1
    for node in range(1, n+1):
        if uses[node]:
            continue
        graph_i = next_graph_i
        check(node)
        next_graph_i = graph_i + 1

    out = graph_i - 1
    print(out)

if True:
    n, m = map(int, input().split(" "))
    a_s = []
    b_s = []
    for i in range(m):
        a, b = map(int, input().split(" "))
        a_s.append(a)
        b_s.append(b)
else:
    import random
    n = random.randint(2, 100000)
    m = random.randint(1, 100000)
    
    a_s = []
    b_s = []
    for i in range(m):    
        a = random.randint(1, n-1)
        b = random.randint(a+1, n)
        a_s.append(a)
        b_s.append(b)

main(a_s, b_s, n, m)

Solution (Python):
n, m = map(int, input().split())
nodes = [[] for _ in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    nodes[a].append(b)
    nodes[b].append(a)

nodes_flag = [False for _ in range(n)]
count = 0
for i in range(n):
    
    if nodes_flag[i] is not True:
        count += 1
        nodes_flag[i] = True
        nodes_list = nodes[i]
        while len(nodes_list):
            new_nodes_list =[]
            for node in nodes_list:
                if nodes_flag[node]:
                    continue
                nodes_flag[node] = True
                for next_node in nodes[node]:
                    new_nodes_list.append(next_node)
            nodes_list = new_nodes_list
print(count-1)

Solution (Python):
N, M = map(int, input().split())
AB = [list(map(int, input().split())) 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())


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

print(u.group_count() - 1)

Solution (Python):
import sys
import math
import itertools
import bisect
from copy import copy,deepcopy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

class UnionFind:
  def __init__(self,n):
    self.n=[-1]*n
    self.r=[0]*n
  def find_root(self,x):
    if self.n[x]<0:
      return x
    else:
      self.n[x]=self.find_root(self.n[x])
      return self.n[x]
  def unite(self,x,y):
    x=self.find_root(x)
    y=self.find_root(y)
    if x==y:return
    elif self.r[x]>self.r[y]:
      self.n[x]+=self.n[y]
      self.n[y]=x
    else:
      self.n[y]+=self.n[x]
      self.n[x]=y
      if self.r[x]==self.r[y]:
        self.r[y]+=1
  def root_same(self,x,y):
    return self.find_root(x)==self.find_root(y)
  def count(self,x):
    return -self.n[self.find_root(x)]

N,M = I()
u = UnionFind(N)
for i in range(M):
    a,b = I()
    u.unite(a-1,b-1)
li = []
q = []
ans = 0
for i in range(N):
    num = u.count(i)
    if num not in li:
        li.append(num)
    q.append(num)
for i in li:
    ans += q.count(i)//i
print(ans-1)

Solution (Python):
from collections import deque

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

AB = [[] for _ in range(N)]

for _ in range(M):
    a,b = map(lambda x: int(x)-1, input().split())
    AB[a].append(b)
    AB[b].append(a)

visited = [0] * N
ans = []
for i in range(N):
    if visited[i]:
        continue
    group = [i]
    d = deque(AB[i])
    while d:
        s = d.popleft()
        if visited[s]:
            continue
        visited[s] = 1
        group.append(s)
        for k in AB[s]:
            d.append(k)
    ans.append(len(group))

print(len(ans)-1)

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

    def find(self, x):
        if self.par[x] < 0:
            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 x == y:
            return
        else:
            if self.rank[x] < self.rank[y]:
                self.par[y] += self.par[x]
                self.par[x] = y
            else:
                self.par[x] += self.par[y]
                self.par[y] = x
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

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

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


n, m = map(int, input().split())
uf = UnionFind(n)
for _ in range(m):
    a, b = map(int, input().split())
    uf.union(a, b)
st = set()
for i in range(1, n+1):
    st.add(uf.find(i))
print(len(st)-1)

Solution (Python):
class path_compressed_quick_union:
    def __init__(self, n):
        self.n = n
        self.data = [i for i in range(n)]
        self.size = [1 for i in range(n)]

    def root(self, p):
        while p != self.data[p]:
            self.data[p] = self.data[self.data[p]]
            p = self.data[p]
        return p

    def connected(self, p, q):
        return self.root(p) == self.root(q)

    def union(self, p, q):
        proot = self.root(p)
        qroot = self.root(q)
        if self.size[proot] < self.size[qroot]:
            self.data[qroot] = proot
            self.size[qroot] += self.size[proot]
        else:
            self.data[proot] = qroot
            self.size[proot] += self.size[qroot]



N, M = map(int,input().split())
uf = path_compressed_quick_union(N)
for i in range(M):
    a,b=map(int,input().split())
    uf.union(a-1,b-1)
ans = []
for i in range(N):
    ans.append(uf.root(i))
print(len(set(ans))-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())
uf = UnionFind(N)






graph = [[] for _ in range(N)]

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

print(uf.group_count()-1)

Solution (Python):
import math
import collections
import itertools
import copy

def YesNo(Bool):
    if(Bool):
        print("YES")
    else:
        print("NO")
    return

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())

def resolve():

    N,M=map(int,input().split())
    A=[0]*M
    B=[0]*M

    uf = UnionFind(N)
    for i in range(M):
        A[i],B[i]=map(int,input().split())
        uf.union(A[i]-1, B[i]-1)
        
    
    

    cnt=uf.group_count()

    print(cnt-1)

resolve()

Solution (Python):
n, m = map(int, input().split())
par = [i for i in range(n)]
import sys
sys.setrecursionlimit(1000000)

def find(x, par):
    if par[x] == x:
        return x
    else:
        a = find(par[x], par)
        par[x] =a
        return a

def unite(x, y):
    x = find(x, par)
    y = find(y, par)
    if x != y:
        par[x] = y

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

groups= 0
for i in range(n):
    if i == par[i]:
        groups +=1
print(groups-1)

Solution (Python):


"""
Created on Sat Sep 26 17:37:27 2020

@author: divyarth
"""

import sys
import heapq
import math





from collections import deque
from collections import defaultdict
from collections import Counter

modH=int(10**9)+7

I=lambda : list(map(int,input().split(' ')))
def PRINT(lst,sep=' '): print(sep.join(map(str,lst)))

n,m=I()
edges=[I() for i in range(m)]
graph=[[] for i in range(n)]

for src,des in edges:
    graph[src-1].append(des-1)
    graph[des-1].append(src-1)

def bfs(node):
    queue=deque()
    queue.append(node)
    while queue:
        cur=queue.popleft()
        for w in graph[cur]:
            if visited[w]==None:
                queue.append(w)
                visited[w]=1

visited=[None]*n
cmp=0
for i in range(n):
    if visited[i]==None:
        bfs(i)
        cmp+=1

print(cmp-1)

Solution (Python):
from collections import Counter


def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


def unite(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:

        if par[x] > par[y]:
            x, y = y, x
        par[x] += par[y]
        par[y] = x
        return True


def size(x):
    return -par[find(x)]


N, M = map(int, input().split())
par = [-1]*N

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

count = 0
for i in par:
    count += i < 0

print(count-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())

def resolve():
    import sys

    input = sys.stdin.readline

    n, m = [int(x) for x in input().rstrip().split(" ")]

    uf = UnionFind(n)

    for i in range(m):
        a, b = [int(x) for x in input().rstrip().split(" ")]
        uf.union(a-1, b-1)

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


if __name__ == "__main__":
    resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2 * (10 ** 6))
n, m = map(int, input().split())
edges = [[] for i in range(n)]
visit = [False for i in range(n)]
def dfs(v):
    visit[v] = True
    for i in edges[v]:
        if not visit[i]:
            dfs(i)
for i in range(m):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
cnt = 0
for i in range(n):
    if not visit[i]:
        dfs(i)
        cnt += 1
print(cnt - 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())
uf = UnionFind(N+1)
for _ in range(M):
    A, B = map(int, input().split())
    uf.union(A, B)

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