Problem p03108 (python)

Fixed submission:
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = s_inpl()   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

############
############
############

class UnionFind(object):
 
    def __init__(self, N):
        self.N = N
        self.parent = list(range(self.N))
        self.rank = [0] * self.N
        self.size = [1] * self.N
 
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
 
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
 
        if self.rank[x] < self.rank[y]:
            x, y = y, x
 
        self.size[x] += self.size[y]
        self.parent[y] = x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def count(self, x):
        return self.size[self.find(x)]

n,m = map(int,input().split())
a = [list(map(int,input().split())) for i in range(m)]

uni = UnionFind(n)
ans = []
kota = n*(n-1)/2
ans.append(kota)
for i in range(m-1,0,-1):
    x,y = a[i]
    x-=1;y-=1
    xs = uni.count(x)
    ys = uni.count(y)
    if uni.find(x) == uni.find(y):
      ans.append(kota)
      continue
    uni.union(x,y)
    kota -= ys*xs
    ans.append(kota)
for i in ans[::-1]:
  print(int(i))

Buggy submission (verdict: Runtime Error):
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = s_inpl()   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

############
############
############

class UnionFind:
    
    def __init__(self, N):
        # 初期は全てが根
        self.parent = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    # データxが属する木の根を求める
    def root_find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.root_find(self.parent[x])
        return self.parent[x]

    # データxが属するグループに属する頂点数を得る
    def count(self, x):
        return self.size[self.root_find(x)]

    # xとyの属する集合を合併
    def unite(self, x, y):
        x_root = self.root_find(x)
        y_root = self.root_find(y)

        if x_root == y_root:
            return 

        if self.rank[x_root] < self.rank[y_root]:
            x_root, y_root = y_root, x_root

        self.size[x_root] += self.size[y_root]
        self.parent[y_root] = x

        if self.rank[x_root] == self.rank[y_root]:
            self.rank[x_root] += 1
    
    # xとyが属する集合が一緒かどうか
    def same(self, x, y):
        return self.root_find(x) == self.root_find(y)            


n,m = map(int,input().split())
a = [list(map(int,input().split())) for i in range(m)]

uni = UnionFind(n)
ans = []
kota = n*(n-1)/2
ans.append(kota)
for i in range(m-1,0,-1):
    x,y = a[i]
    x-=1;y-=1
    xs = uni.count(x)
    ys = uni.count(y)
    if uni.root_find(x) == uni.root_find(y):
      ans.append(kota)
      continue
    uni.unite(x,y)
    kota -= ys*xs
    ans.append(kota)
for i in ans[::-1]:
  print(int(i))

Buggy submission (verdict: Runtime Error):
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = s_inpl()   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

############
############
############

class UnionFind:
    
    def __init__(self, N):
        # 初期は全てが根
        self.parent = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    # データxが属する木の根を求める
    def root_find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.root_find(self.parent[x])
        return self.parent[x]

    # データxが属するグループに属する頂点数を得る
    def count(self, x):
        return self.size[self.root_find(x)]

    # xとyの属する集合を合併
    def unite(self, x, y):
        x_root = self.root_find(x)
        y_root = self.root_find(y)

        if x_root == y_root:
            return 

        if self.rank[x_root] < self.rank[y_root]:
            x_root, y_root = y_root, x_root

        self.size[x_root] += self.size[y_root]
        self.parent[y_root] = x

        if self.rank[x_root] == self.rank[y_root]:
            self.rank[x_root] += 1
    
    # xとyが属する集合が一緒かどうか
    def same(self, x, y):
        return self.root_find(x) == self.root_find(y)            


N, M = l_inpl()
uf = UnionFind(N)

qs = []
for _ in range(M):
    a, b = l_inpl()
    qs.append([a-1, b-1])


prev_cnt = N*(N-1)//2
ans = [prev_cnt]
for i in range(M-1, 0, -1):
    a, b = qs[i]
    diff = uf.count(a) * uf.count(b)
    if uf.same(a, b):
        ans.append(prev_cnt)
        continue
    uf.unite(a, b)
    prev_cnt -= diff
    ans.append(prev_cnt)

for i in ans[::-1]:
    print(i)

Buggy submission (verdict: Runtime Error):
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = s_inpl()   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

############
############
############

class UnionFind:
    
    def __init__(self, N):
        # 初期は全てが根
        self.parent = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    # データxが属する木の根を求める
    def root_find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.root_find(self.parent[x])
        return self.parent[x]

    # データxが属するグループに属する頂点数を得る
    def count(self, x):
        return self.size[self.root_find(x)]

    # xとyの属する集合を合併
    def unite(self, x, y):
        x_root = self.root_find(x)
        y_root = self.root_find(y)

        if x_root == y_root:
            return 

        if self.rank[x_root] < self.rank[y_root]:
            x_root, y_root = y_root, x_root

        self.size[x_root] += self.size[y_root]
        self.parent[y_root] = x

        if self.rank[x_root] == self.rank[y_root]:
            self.rank[x_root] += 1
    
    # xとyが属する集合が一緒かどうか
    def same(self, x, y):
        return self.root_find(x) == self.root_find(y)            


N, M = l_inpl()
uf = UnionFind(N)

qs = []
for _ in range(M):
    a, b = l_inpl()
    qs.append([a-1, b-1])


prev_cnt = N*(N-1)//2
ans = [prev_cnt]
for i in range(M-1, 0, -1):
    a, b = qs[i]
    diff = uf.count(a) * uf.count(b)
    if uf.same(a, b):
        ans.append(prev_cnt)
        continue
    uf.unite(a, b)
    prev_cnt -= diff
    ans.append(prev_cnt)

print("\n".join([str(s) for s in ans[::-1]]))

Buggy submission (verdict: Runtime Error):
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = s_inpl()   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

############
############
############

class UnionFind:
    
    def __init__(self, N):
        # 初期は全てが根
        self.parent = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    # データxが属する木の根を求める
    def root_find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.root_find(self.parent[x])
        return self.parent[x]

    # データxが属するグループに属する頂点数を得る
    def count(self, x):
        return self.size[self.root_find(x)]

    # xとyの属する集合を合併
    def unite(self, x, y):
        x_root = self.root_find(x)
        y_root = self.root_find(y)

        if x_root == y_root:
            return 

        if self.rank[x_root] < self.rank[y_root]:
            x_root, y_root = y_root, x_root

        self.size[x_root] += self.size[y_root]
        self.parent[y_root] = x

        if self.rank[x_root] == self.rank[y_root]:
            self.rank[x_root] += 1
    
    # xとyが属する集合が一緒かどうか
    def same(self, x, y):
        return self.root_find(x) == self.root_find(y)            


N, M = l_inpl()
uf = UnionFind(N)

qs = []
for _ in range(M):
    a, b = l_inpl()
    qs.append([a-1, b-1])


prev_cnt = N*(N-1)//2
ans = [prev_cnt]
for a, b in qs[::-1][:-1]:
    diff = uf.count(a) * uf.count(b)
    if uf.same(a, b):
        ans.append(prev_cnt)
        continue
    uf.unite(a, b)
    prev_cnt -= diff
    ans.append(prev_cnt)

print("\n".join([str(s) for s in ans[::-1]]))

Buggy submission (verdict: Runtime Error):
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = s_inpl()   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

############
############
############

class UnionFind:
    
    def __init__(self, N):
        # 初期は全てが根
        self.parent = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    # データxが属する木の根を求める
    def root_find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.root_find(self.parent[x])
        return self.parent[x]

    # データxが属するグループに属する頂点数を得る
    def count(self, x):
        return self.size[self.root_find(x)]

    # xとyの属する集合を合併
    def unite(self, x, y):
        x_root = self.root_find(x)
        y_root = self.root_find(y)

        if x_root == y_root:
            return 

        if self.rank[x_root] < self.rank[y_root]:
            x_root, y_root = y_root, x_root

        self.size[x_root] += self.size[y_root]
        self.parent[y_root] = x

        if self.rank[x_root] == self.rank[y_root]:
            self.rank[x_root] += 1
    
    # xとyが属する集合が一緒かどうか
    def same(self, x, y):
        return self.root_find(x) == self.root_find(y)            


N, M = l_inpl()
uf = UnionFind(N)

qs = []
for _ in range(M):
    a, b = l_inpl()
    qs.append([a-1, b-1])


ans = [N*(N-1)//2]
for a, b in qs[::-1][:-1]:
    if not uf.same(a, b):
        ans.append(ans[-1] - uf.count(a) * uf.count(b))
        uf.unite(a, b)
    else:
        ans.append(ans[-1])

print("\n".join([str(s) for s in ans[::-1]]))

Buggy submission (verdict: Runtime Error):
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = s_inpl()   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

############
############
############

class UnionFind:
    
    def __init__(self, N):
        # 初期は全てが根
        self.parent = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    # データxが属する木の根を求める
    def root_find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.root_find(self.parent[x])
        return self.parent[x]

    # データxが属するグループに属する頂点数を得る
    def count(self, x):
        return self.size[self.root_Pfind(x)]

    # xとyの属する集合を合併
    def unite(self, x, y):
        x_root = self.root_find(x)
        y_root = self.root_find(y)

        if x_root == y_root:
            return 

        if self.rank[x_root] < self.rank[y_root]:
            x_root, y_root = y_root, x_root

        self.size[x_root] += self.size[y_root]
        self.parent[y_root] = x

        if self.rank[x_root] == self.rank[y_root]:
            self.rank[x_root] += 1
    
    # xとyが属する集合が一緒かどうか
    def same(self, x, y):
        return self.root_find(x) == self.root_find(y)            


N, M = l_inpl()
uf = UnionFind(N)

qs = []
for _ in range(M):
    a, b = l_inpl()
    qs.append([a-1, b-1])


ans = [N*(N-1)//2]
for a, b in qs[::-1][:-1]:
    if not uf.same(a, b):
        ans.append(ans[-1] - uf.count(a) * uf.count(b))
        uf.unite(a, b)
    else:
        ans.append(ans[-1])

print("\n".join([str(s) for s in ans[::-1]]))

Buggy submission (verdict: Runtime Error):
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = s_inpl()   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

############
############
############

class UnionFind:
    
    def __init__(self, N):
        # 初期は全てが根
        self.parent = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    # データxが属する木の根を求める
    def root_find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.root_find(self.parent[x])
        return self.parent[x]

    # データxが属するグループに属する頂点数を得る
    def count(self, x):
        return self.size[self.root_Pfind(x)]

    # xとyの属する集合を合併
    def unite(self, x, y):
        x_root = self.root_find(x)
        y_root = self.root_find(y)

        if x_root == y_root:
            return 

        if self.rank[x_root] < self.rank[y_root]:
            x_root, y_root = y_root, x_root

        self.size[x_root] += self.size[y_root]
        self.parent[y_root] = x

        if self.rank[x_root] == self.rank[y_root]:
            self.rank[x_root] += 1
    
    # xとyが属する集合が一緒かどうか
    def same(self, x, y):
        return self.root_find(x) == self.root_find(y)            


N, M = l_inpl()
uf = UnionFind(N)

qs = []
for _ in range(M):
    a, b = l_inpl()
    qs.append([a-1, b-1])


ans = [N*(N-1)//2]
for a, b in qs[::-1][:-1]:
    if not uf.same(a, b):
        ans.append(ans[-1] - uf.count(a) * uf.count(b))
        uf.unite(a, b)
    else:
        ans.append(ans[-1])

print("\n".join([str(s) for s in ans[::-1]]))