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: Accepted

Solution code:
class DisjointSet:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0]*size
    
    def find(self, x):
        stack = []
        parent = self.parent
        while parent[x] != x:
            stack.append(x)
            x = parent[x]
        for y in stack:
            parent[y] = x
        return x

    def union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        
        if self.rank[xr] > self.rank[yr]:
            self.parent[yr] = xr
        elif self.rank[xr] < self.rank[yr]:
            self.parent[xr] = yr
        elif xr != yr:
            self.parent[yr] = xr
            self.rank[xr] += 1

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

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

print(len(set(ds.find(i) for i in range(N)))-1)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
adj = [[] for _ in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    adj[A].append(B)
    adj[B].append(A)

def grouping(adj):
    "0-indexed の無向グラフを連結成分に分解する。"
    n = len(adj)
    ret = [-1] * n
    g = 0
    for v in range(n):
        if ret[v] == -1:
            ret[v] = g
            stack = [v]
            while stack:
                v = stack.pop()
                for nv in adj[v]:
                    if ret[nv] == -1:
                        ret[nv] = ret[v]
                        stack.append(nv)
            g += 1
    return ret

print(max(grouping(adj)))

Submission status: Accepted

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

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

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

    def unite(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1

    def get_size(self, x):
        return -self.table[self._root(x)]


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

ans = 0
for p in uft.table:
    if p < 0:
        ans += 1
print(ans - 1)

Submission status: Accepted

Solution code:
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)
print(UF.group_count() - 1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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()}

(n, m), *d = [[*map(int, o.split())] for o in open(0)]
UF = UnionFind(n)
for a, b in d:
    UF.union(a-1, b-1)
print(UF.group_count()-1)

Submission status: Accepted

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズ
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

N, M = map(int, input().split())
uni = UnionFind(N+1)
for _ in range(M):
    a, b = map(int, input().split())
    uni.Unite(a, b)

R = set()
for i in range(1, N+1):
    R.add(uni.Find_Root(i))

print(len(R)-1)

Submission status: Accepted

Solution code:
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)
for _ in range(M):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)

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

Submission status: Accepted

Solution code:
class UnionFind:
    #def   -> foo=UnionFind(n,1)  <- 1-based index, default is 0
    #method -> foo.hoge(huga)
    __slots__ = ["_size", "_first_idx", "_parents"]
    def __init__(self, size: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [-1] * (size + first_index)
    def find(self, x: int) -> int:
        if self._parents[x] < 0:
            return x
        news=[]
        p=self._parents
        y=p[x]
        while y>=0:
            news.append(x);x,y=y,p[y]
        if len(news)!=1:
            for P in news:p[P]=x
        return x

    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)
    def unite(self, x: int, y: int) -> bool:
        x, y = self.find(x), 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: int) -> int:
        return -self._parents[self.find(x)]
    def group_count(self) ->int:
        return sum(1 for i in  self._parents if i<0)-self._first_idx
    def connected(self) ->bool:
        return self._parents[self.find(self._first_idx)]==-self._size
n,m=map(int,input().split())
uf=UnionFind(n,1)
for i in range(m):
    a,s=map(int,input().split())
    uf.unite(a,s)
print(uf.group_count()-1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

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

class UnionFind:
    def __init__(self,n):
        self.par=[i for i in range(n)]
        self.siz=[1]*n
        
    def root(self,x):
        while self.par[x]!=x:
            self.par[x]=self.par[self.par[x]]
            x=self.par[x]
        return x
    
    def unite(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if x==y:
            return False
        if self.siz[x]<self.siz[y]:
            x,y=y,x
        self.siz[x]+=self.siz[y]
        self.par[y]=x
        return True
    
    def is_same(self,x,y):
        return self.root(x)==self.root(y)
    
    def size(self,x):
        return self.siz[self.root(x)]

u=UnionFind(N)
for _ in range(M):
    a,b=map(int1,input().split())
    u.unite(a,b)
ans=0
s=set()
for i in range(N):
    s.add(u.root(i))
print(len(s)-1)

Submission status: Accepted

Solution code:
# UnionFind
import sys
sys.setrecursionlimit(1000000)
class UnionFind:
  def __init__(self, n):
    self.n = [-1]*n
    self.r = [0]*n
    self.siz = 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
    self.siz -= 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)]

  def size(self):
    return self.siz

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

Submission status: Runtime Error

Solution code:
from collections import Counter
n,m = map(int,input().split())
c = [0]*(n+1)
ans = []
for _ in range(m):
    tmp = list(map(int,input().split()))
    tmp.sort()
    ans.append(tmp)
ans.sort()
c[ans[0][0]]=ans[0][0]
for i in ans:
    print(i)
    if i[0]==ans[0][0]:
        c[i[1]]=i[0]
    else:
        if c[i[1]]<=c[i[0]] and c[i[1]]!=0:
            c[i[0]]=c[i[1]]
        elif c[i[0]]<=c[i[1]] and c[i[0]]!=0:
            c[i[1]]=c[i[0]]
        else:
            c[i[0]]=i[0]
            c[i[1]]=i[0]
    print(c)
cnt = Counter(c)
cnt = cnt.most_common()
a = n
for i in cnt:
    if i[0][0]!=0:
        if i[0][1]>1:
            a-=i[0][1]
        a+=1
print(a-1)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
g=[[],]*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
def dfs(u):
	if vis[u]:
		return
	vis[u]=True
	for v in g[u]:
		dfs(v)

cnt=0
for i in range(n):
	if not vis[i]:
		cnt+=1
		dfs(i)
print(cnt-1)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
ab_list = [list(map(int,input().split())) for nesya in range(m)]
ab_list = sorted(ab_list)
hoge = [1 for motsu in range(n) ]
hoge[0] = 0
for ab in ab_list:
  hoge[ab[1]] = 0
print(sum(hoge))

Submission status: Runtime Error

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

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

def union_find(x):
    if par[x] == x:
        return x
    else:
        return union_find(par[x])

for i in range(m):
    ai, bi = map(int, input().split(' '))
    root = union_find(ai)
    par[bi] = root
cnt = 0
for i in range(2, n+1):
    root_i = union_root(i)
    if root_i != 1:
        cnt += 1
        par[root_i] = 1

print(cnt)

Submission status: Runtime Error

Solution code:
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 roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
      
    def group_count(self):
        return len(self.roots())

n, m = map(int, input().split())
un = UnionFind(n)
for _ in range(m):
    a, b = map(int, input().split())
    un.union(a, b)
print(un.group_count() - 1)

Submission status: Runtime Error

Solution code:
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 roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
      
    def group_count(self):
        return len(self.roots)

n, m = map(int, input().split())
un = UnionFind(n)
for _ in range(m):
    a, b = map(int, input().split())
    un.union(a, b)
print(un.group_count() - 1)

Submission status: Runtime Error

Solution code:
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os
    import re
    with open(__file__) as f:
        source = f.read().split('###''nbacl')
    for s in source[1:]:
        s = re.sub("'''.*", '', s)
        sp = s.split(maxsplit=1)
        if os.path.dirname(sp[0]):
            os.makedirs(os.path.dirname(sp[0]), exist_ok=True)
        with open(sp[0], 'w') as f:
            f.write(sp[1])
    from nbmodule import cc    cc.compile()import numpy as np
from numpy import int64
from nbmodule import solve


f = open(0)
N, M = [int(x) for x in f.readline().split()]
AB = np.fromstring(f.read(), dtype=int64, sep=' ').reshape((-1, 2))
ans = solve(N, AB)
print(ans)

'''
###nbacl nbmodule.py
import numpy as np
from numpy import int64
from numba import njit
from numba.types import i8
from numba.pycc import CC
import nbacl.dsu as dsu
cc = CC('nbmodule')


@cc.export('solve', (i8, i8[:, ::1]))
def solve(N, AB):
    t = np.full(N, -1, dtype=int64)
    for i in range(AB.shape[0]):
        dsu.merge(t, AB[i, 0], AB[i, 1])
    ret = 0
    for _ in dsu.groups(t):
        ret += 1
    return ret

if __name__ == '__main__':
    cc.compile()

###nbacl nbacl/dsu.py
import numpy as np
from numpy import int64
from numba import njit


@njit
def dsu(t):
    t = -1


@njit
def merge(t, x, y):
    u = leader(t, x)
    v = leader(t, y)

    if u == v:
        return u

    if -t[u] < -t[v]:
        u, v = v, u

    t[u] += t[v]
    t[v] = u

    return u


@njit
def same(t, x, y):
    return leader(t, x) == leader(t, y)


@njit
def leader(t, x):
    if t[x] < 0:
        return x
    t[x] = leader(t, t[x])
    return t[x]


@njit
def size(t, x):
    return -t[leader(t, x)]


@njit
def groups(t):
    for i in range(t.shape[0]):
        if t[i] < 0:
            yield i

'''

Submission status: Runtime Error

Solution code:
n, m = map(int ,input().split())
graph = [[] for _ in range(n)]
for i in range(m):
  a,b = map(int, input().split())
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
v = [0]*n
def dfs(node):
  v[node] = 1
  for i in graph[node]:
    if v[i] == 0: dfs(i)
dfs(0)
ans = 0
for i in range(n):
  if v[i] == 0: dfs(i); ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin
input = stdin.readline
count = 0
def solve():
    n,m = map(int,input().split())
    p = [tuple(map(int,inp.split())) for inp in stdin.read().splitlines()]
    father = [-1] * n    # store the opposite of members in the union
    count = n
    def getfather(x):
        if father[x] < 0: return x
        father[x] = getfather(father[x])
        return father[x]


    def union(x, y):
        x = getfather(x)
        y = getfather(y)
        nonlocal count
        if x != y:
            count -= 1
            if father[x] > father[y]:
                x,y = y,x
            father[x] += father[y]
            father[y] = x
    for a,b in p:
        union(a,b)
    print(count - 1)

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
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())
         uf.union(a,b)
         

print(uf.group_count() - 1)

Submission status: Runtime Error

Solution code:
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())
         uf.union(a,b)
         

print(uf.group_count() - 1)

Submission status: Runtime Error

Solution code:
import collections
n,con = map(int,input().split())
graph = collections.defaultdict(list)
for i in range(con):
    u,v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

visited = [0]*(n+1)
def dfs(nodes):
    for i in nodes:
        if visited[i]!=1:
            visited[i]= 1
            dfs(graph[i])

connected = 0
missing = 0
for i in range(1,n+1):
    if i in graph and visited[i]!=1:
        visited[i]=1
        connected += 1
        dfs(graph[i])
    if i not in graph:
        missing+=1
print(connected-1+missing)

Submission status: Runtime Error

Solution code:
import collections
n,con = map(int,input().split())
graph = collections.defaultdict(list)
for i in range(con):
    u,v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

visited = set()
def dfs(nodes):
    for i in nodes:
        if i not in visited:
            visited.add(i)
            dfs(graph[i])

connected = 0
missing = 0
for i in range(1,n+1):
    if i in graph and i not in visited:
        visited.add(i)
        dfs(graph[i])
        connected += 1
    if i not in graph:
        missing+=1
print(connected-1+missing)

Submission status: Runtime Error

Solution code:
import collections
n,con = map(int,input().split())
graph = collections.defaultdict(list)
for i in range(con):
    u,v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

visited = set()
def dfs(nodes):
    for i in nodes:
        if i not in visited:
            visited.add(i)
            dfs(graph[i])

connected = 0
missing = 0
for i in range(1,n+1):
    if i in graph and i not in visited:
        connected += 1
        dfs(graph[i])
    if i not in graph:
        missing+=1
print(connected-1+missing)

Submission status: Runtime Error

Solution code:
from sys import setrecursionlimit
class UnionFind:
    setrecursionlimit(10**6)
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]  # 親
        self.rank = [1] * n  # 木の高さ
        self.size = [1] * n  # size[i] は i を根とするグループのサイズ

    def find(self, x):  # x の根を返す
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])  # 経路圧縮
            return self.parent[x]

    def unite(self, x, y):  # x, y の属する集合を併合する
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1
    def roots(self):  # すべての根をリストで返す
        return [i for i, x in enumerate(self.parent) if i == x]

N,M = map(int,input().split())
uf = UnionFind(N)
for i in range(M):
    a,b = map(int,input().split())
    uf.unite(a,b)
ans = len(uf.roots())-1
print(ans)

Submission status: Runtime Error

Solution code:
from sys import setrecursionlimit
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]  # 親
        self.rank = [1] * n  # 木の高さ
        self.size = [1] * n  # size[i] は i を根とするグループのサイズ

    def find(self, x):  # x の根を返す
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])  # 経路圧縮
            return self.parent[x]

    def unite(self, x, y):  # x, y の属する集合を併合する
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1
    def roots(self):  # すべての根をリストで返す
        return [i for i, x in enumerate(self.parent) if i == x]
setrecursionlimit(10**6)
N,M = map(int,input().split())
uf = UnionFind(N)
for i in range(M):
    a,b = map(int,input().split())
    uf.unite(a,b)
ans = len(uf.roots())-1
print(ans)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]  # 親
        self.rank = [1] * n  # 木の高さ
        self.size = [1] * n  # size[i] は i を根とするグループのサイズ

    def find(self, x):  # x の根を返す
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])  # 経路圧縮
            return self.parent[x]

    def unite(self, x, y):  # x, y の属する集合を併合する
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1
    def roots(self):  # すべての根をリストで返す
        return [i for i, x in enumerate(self.parent) if i == x]
N,M = map(int,input().split())
uf = UnionFind(N)
for i in range(M):
    a,b = map(int,input().split())
    uf.unite(a,b)
ans = len(uf.roots())-1
print(ans)

Submission status: Runtime Error

Solution code:
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] = [int(i) for i in input().split()]
uf = UnionFind(N)
for j in range(M):
    [A, B] = [int(i) for i in input().split()]
    uf.union(A, B)
print(uf.group_count() - 1)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())

R=list(range(N))
G=[]
for _ in range(M):
    a,b=map(int,input().split())
    R.remove(a)
    R.remove(b)

    flg=True
    n=0
    buf=None
    for i in range(len(G)):
        if a in G[i] and b in G[i]:
            flg=False
            break
        elif a not in G[i] or b not in G[i]:
            pass
        elif a in G[i]:
            n+=1
            flg=False
            if n == 2:
                G[i] = G[i].extend(G.pop(buf))
                break
            else:
                buf=i
                G[i].append(b)
        else:
            n+=1
            flg=False
            if n == 2:
                G[i] = G[i].extend(G.pop(buf))
                break
            else:
                buf=i
                G[i].append(a)
    if flg:
        G.append([a,b])

print(len(G) + len(R) - 1)

Submission status: Runtime Error

Solution code:
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 roots(self):
      return [i for i, x in enumerate(self.parents) if x < 0]
    
    def group_count(self):
      return len(self.roots())
    
n,m = map(int,input().split())  
uf = UnionFind(n)

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

Submission status: Runtime Error

Solution code:
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 main():
    N,M = map(int,input().split())
    uf = UnionFind(N)
    for i in range(M):
        a, b = map(int,input().split())
        uf.union(a,b)
    print(uf.group_count()-1)
main()