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



Sample input:
3 1
1 2


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
        self._size = [1]*N
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_sama(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
            self._size[rb] += self._size[ra]
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]:
                self.rank[ra] += 1
            self._size[ra] += self._size[rb]
        self.count += 1
    def print_info(self):
        print("parent", self.parent)
        print("rank", self.rank)
        print("count", self.count)
        print("size", self._size)
    def size(self,a):
        return self._size[self.root(a)]

import sys
input = sys.stdin.readline
ans = 0
N,M = map(int,input().split())
UF = UnionFind(N)
for i in range(M):
    A,B = map(int,input().split())
    A -= 1
    B -= 1
    UF.unite(A,B)

for i in range(N):
    for j in range(i+1,N):
        if not UF.is_sama(i,j):
            ans += 1
            UF.unite(i,j)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
N, M = map(int, input().split())
G = [[] for _ in range(N)]
seen = [False] * N

for _ in range(M):
    A, B = map(lambda x: int(x) - 1, input().split())
    G[A].append(B)
    G[B].append(A)


def dfs(x, G, seen, before):
    seen[x] = True
    for next in G[x]:
        if next == before:
            continue
        if seen[next]:
            continue
        dfs(next, G, seen, x)

ans = 0
for i in range(N):
    if seen[i]:
        continue
    dfs(i, G, seen, -1)
    ans += 1
    for j in range(N):
        seen[i] = False

print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
mat=[[0]*n for i in range(n)]
for i in range(n):
    mat[i][i]=1
for i in range(m):
    x,y=map(int,input().split())
    mat[x][y]=1
    mat[y][x]=1
out=0
for i in range(n):
    if mat[i].count(1)==1:
        out+=1
print(out)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
data=list(range(n))
cnt=n-1
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    while data[a]!=a:
        a=data[a]
    while data[b]!=b:
        b=data[b]
    if a!=b:
        data[a]=b
        cnt-=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
r=sys.stdin.readline
N,M=map(int,r().split())
city=[[] for _ in range(N+1)]
for _ in range(M):
    a,b=map(int,r().split())
    city[a].append(b)
    city[b].append(a)
check=[True]+[False]*(N)
def dfs(v):
    stack=[v]
    visited=[False]*(N+1)
    visited[v]=True
    while stack:
        cur=stack.pop()
        check[cur]=True
        for v in city[cur]:
            if not visited[v]:
                stack.append(v)
cnt=0
for i in range(1,N+1):
    if not check[i]:
        dfs(i)
        cnt+=1
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int,input().split())
lst = [-1 for i in range(n + 1)]
lst[0] = 0
def find (x):
    if (lst[x] < 0):
        return(x)
    else:
        return (find(lst[x]))
def unit(x, y):
    xp = find(x)
    yp = find(y)
    if (xp == yp):
        pass
    else:
        lst[yp] = xp
for i in range(m):
    a, b = map(int,input().split())
    unit(a, b)

ans = -1
for i in range(n + 1):
    if (lst[i] == -1):
        ans = ans + 1

print(ans)

Submission status: Time Limit Exceeded

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

par = [i for i in range(n+1)]
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y

L=[[0 for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    unite(a,b)

print(len(set(par))-2)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int,input().split())
M = [[0 for _ in range(n)] for i in range(n)]
for i in range(m):
    a, b = map(int,input().split())
    M[a][b] = 1
    M[b][a] = 1
    
cnt = 0   
for i in range(n-1):
    if all(M[i][j] == 0 for j in range(1+i, n)):
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

n, m = map(int, input().split())
g = np.array([[0 for i in range(n)] for i in range(n)])

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

print(connected_components(g, return_labels=False) - 1)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
        self._size = [1]*N
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_sama(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
            self._size[rb] += self._size[ra]
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]:
                self.rank[ra] += 1
            self._size[ra] += self._size[rb]
        self.count += 1
    def print_info(self):
        print("parent", self.parent)
        print("rank", self.rank)
        print("count", self.count)
        print("size", self._size)
    def size(self,a):
        return self._size[self.root(a)]

import sys
input = sys.stdin.readline
ans = 0
N,M = map(int,input().split())
UF = UnionFind(N)
for i in range(M):
    A,B = map(int,input().split())
    A -= 1
    B -= 1
    UF.unite(A,B)

for i in range(N):
    for j in range(i+1,N):
        if not UF.is_sama(i,j):
            ans += 1
            UF.unite(i,j)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


class Graph:
    # init function to declare class variables
    def __init__(self, V):
        self.V = V
        self.adj = [[] for i in range(V)]

    def DFSUtil(self, temp, v, visited):

        # Mark the current vertex as visited
        visited[v] = True

        # Store the vertex to list
        temp.append(v)

        # Repeat for all vertices adjacent
        # to this vertex v
        for i in self.adj[v]:
            if visited[i] == False:
                # Update the list
                temp = self.DFSUtil(temp, i, visited)
        return temp

        # method to add an undirected edge

    def addEdge(self, v, w):
        self.adj[v].append(w)
        self.adj[w].append(v)

        # Method to retrieve connected components

    # in an undirected graph
    def connectedComponents(self):
        visited = []
        cc = []
        for i in range(self.V):
            visited.append(False)
        for v in range(self.V):
            if visited[v] == False:
                temp = []
                cc.append(self.DFSUtil(temp, v, visited))
        return cc

        # Driver Code


if __name__ == "__main__":
    # Create a graph given in the above diagram
    # 5 vertices numbered from 0 to 4
    # g = Graph(5);
    # g.addEdge(1, 0)
    # g.addEdge(2, 3)
    # g.addEdge(3, 4)



    n,m = MAP()

    g = Graph(n)

    for _ in range(m):
        u,v = MAP()
        g.addEdge(u-1,v-1)
        g.addEdge(v-1,u-1)
    print(len(g.connectedComponents()) - 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, m = map(int,input().split())

edge = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
    
visited = [0]*n
visited[0] = 1
q = deque([0])

ans = 0

while sum(visited) < n:
    while q:
        now = q.popleft()
        for to in edge[now]:
            if visited[to] == 0:
                q.append(to)
                visited[to] = 1
    #print(visited)
    if sum(visited) < n:
        ans += 1
        for i,v in enumerate(visited):
            if v == 0:
                q.append(i)
                visited[i] = 1
                break

print(ans)

Submission status: Memory Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip('\r\n')
sys.setrecursionlimit(10**9)

from collections import defaultdict

n,m = (int(x) for x in input().split())
visited = [False for _ in range(n)]

graph = defaultdict(list)

def dfs(node):
    visited[node] = True
    for next_node in graph[node]:
        if not visited[next_node]:
            dfs(next_node)

for _ in range(m):
    u,v = (int(x) - 1 for x in input().split())
    graph[u].append(v)
    graph[v].append(u)
ans = -1
for i in range(n):
    if not visited[i]:
        dfs(i)
        ans += 1
print(ans)

Submission status: Memory Limit Exceeded

Solution code:
import os
import sys
from atexit import register
from io import BytesIO
sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))
input = lambda: sys.stdin.readline().rstrip('\r\n')
raw_input = lambda: sys.stdin.readline().rstrip('\r\n')
sys.setrecursionlimit(10**9)

from collections import defaultdict

n,m = (int(x) for x in input().split())
visited = [False for _ in xrange(n)]

graph = defaultdict(list)

def dfs(node):
    visited[node] = True
    for next_node in graph[node]:
        if not visited[next_node]:
            dfs(next_node)

for _ in xrange(m):
    u,v = (int(x) - 1 for x in input().split())
    graph[u].append(v)
    graph[v].append(u)
ans = -1
for i in xrange(n):
    if not visited[i]:
        dfs(i)
        ans += 1
print(ans)

Submission status: Memory Limit Exceeded

Solution code:
import os
import sys
from atexit import register
from io import BytesIO
sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))
input = lambda: sys.stdin.readline().rstrip('\r\n')
raw_input = lambda: sys.stdin.readline().rstrip('\r\n')
sys.setrecursionlimit(10**9)


n,m = (int(x) for x in input().split())
visited = [False for _ in xrange(n)]

graph = dict(((i,[]) for i in xrange(n)))

def dfs(node):
    visited[node] = True
    for next_node in graph[node]:
        if not visited[next_node]:
            dfs(next_node)

for _ in xrange(m):
    u,v = (int(x) - 1 for x in input().split())
    graph[u].append(v)
    graph[v].append(u)
ans = -1
for i in xrange(n):
    if not visited[i]:
        dfs(i)
        ans += 1
print(ans)

Submission status: Memory Limit Exceeded

Solution code:
import os
import sys
from atexit import register
from io import BytesIO
sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))
input = lambda: sys.stdin.readline().rstrip('\r\n')
raw_input = lambda: sys.stdin.readline().rstrip('\r\n')
sys.setrecursionlimit(10**9)


n,m = (int(x) for x in input().split())
visited = [False for _ in xrange(n)]

graph = dict(((i,[]) for i in xrange(n)))

def dfs(node):
    # global visited
    if visited[node]:
        return
    visited[node] = True
    for next_node in graph[node]:
        dfs(next_node)

for _ in xrange(m):
    u,v = (int(x) - 1 for x in input().split())
    graph[u].append(v)
    graph[v].append(u)
ans = -1
for i in xrange(n):
    if not visited[i]:
        dfs(i)
        ans += 1
print(ans)

Submission status: Memory Limit Exceeded

Solution code:
import os
import sys
from atexit import register
from io import BytesIO
sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))
input = lambda: sys.stdin.readline().rstrip('\r\n')
raw_input = lambda: sys.stdin.readline().rstrip('\r\n')
sys.setrecursionlimit(10**9)


n,m = (int(x) for x in input().split())
visited = [False for _ in xrange(n)]

graph = dict(((i,[]) for i in xrange(n)))

def dfs(node):
    # global visited
    if visited[node]:
        return
    visited[node] = True
    for next_node in graph[node]:
        dfs(next_node)

for i in xrange(n):
    graph[i] = []
for _ in xrange(m):
    u,v = (int(x) - 1 for x in input().split())
    graph[u].append(v)
    graph[v].append(u)
ans = -1
for i in xrange(n):
    if not visited[i]:
        dfs(i)
        ans += 1
print(ans)

Submission status: Memory Limit Exceeded

Solution code:
def main():
    import sys
    N,M=list(map(int,sys.stdin.readline().split()))
    dic=[[] for _ in range(100001)]
    sys.setrecursionlimit(100001)
    mark=[0]*N
    for i in range(M):
        A,B=list(map(int,sys.stdin.readline().split()))
        dic[A-1].append(B-1)
        dic[B-1].append(A-1)
    def dfs(idx):
        if mark[idx]:
            return
        mark[idx]=1
        for a in dic[idx]:
            dfs(a)

    i=0
    count=0
    while True:
        if not mark[i]:
            count+=1
            dfs(i)
        i+=1
        if i==N:
            break
    
    print(count-1)
main()

Submission status: Memory Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
N, M = map(int, input().split())
G = [[] for _ in range(N)]
seen = [False] * N

for _ in range(M):
    A, B = map(lambda x: int(x) - 1, input().split())
    G[A].append(B)
    G[B].append(A)


def dfs(x, G, seen, before):
    seen[x] = True
    for next in G[x]:
        if next == before:
            continue
        if seen[next]:
            continue
        dfs(next, G, seen, x)

ans = 0
for i in range(N):
    if seen[i]:
        continue
    dfs(i, G, seen, -1)
    ans += 1

print(ans-1)

Submission status: Memory Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
def f(p, c):
    if P[p] == 0:
        P[p] = c
        for j in range(len(F[p])):
            f(F[p][j], c)
N, M = map(int, input().split())
F = [[] for _ in range(N)]
P = [0] * N
for i in range(M):
    A, B = map(int, input().split())
    F[A-1].append(B-1)
    F[B-1].append(A-1)
c=0
for i in range(N):
    if P[i] == 0:
        c+=1
        f(i, c)
print(c-1)

Submission status: Memory Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 26 17:37:27 2020

@author: divyarth
"""

import sys
import heapq
import math

sys.setrecursionlimit(100000)
#input=sys.stdin.readline
#print=sys.stdout.write

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 dfs(node):
    visited[node]=1
    for w in graph[node]:
        if visited[w]==None:
            dfs(w)

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

print(cmp-1)

Submission status: Memory Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
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)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
g=[[] for i in range(n)]
for i in range(m):
	u,v=map(int,input().split())
	u-=1
	v-=1
	g[u].append(v)
	g[v].append(u)

vis=[False]*n
stk=[]

cnt=0
tt=0
for i in range(n):
	if not vis[i]:
		cnt+=1
		stk.append(i)
	while len(stk)!=0:
		u=stk[-1]
		stk.pop()
		if vis[u]:
			continue
		vis[u]=True
		for v in g[u]:
			tt+=1
			if not vis[v]:
				stk.append(v)
print(cnt-1)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
par = [i for i in range(n+1)]

def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮？
        return par[x]

def same(x,y):
    return find(x) == find(y) # Boolでreturn

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

ans = 0
for i in range(m):
    a,b = map(int,input().split())
    unite(a,b)

for i in range(n):
    find(i+1)
par = par[1:]
ans = 0
from collections import Counter
t = Counter(par)
print(len(t)-1)

Submission status: Accepted

Solution code:
class UnionFind():
    """unionFindツリー
    FindとUnionがきも
    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())

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

print(uf.group_count() - 1)

Submission status: Accepted

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

    def find(self, x):
        """要素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が属するグループと要素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):
        """要素xが属するグループのサイズを返す"""
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """要素x, yが同じグループかどうか"""
        return self.find(x) == self.find(y)

    def members(self, x):
        """要素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):
        """print()での表示用"""
        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())
    a, b = a - 1, b - 1
    uf.union(a, b)

print(uf.group_count() - 1)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        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
    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # 要素xが属するグループに属する要素をリストで返す
    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()}
    # print()での表示用
    # all_group_members()をprintする
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N, M = MAP()

uf = UnionFind(N)

for _ in range(M):
    A, B = MAP()
    uf.union(A-1, B-1)

print(uf.group_count()-1)