import sys input = lambda : sys.stdin.readline().rstrip() sys.setrecursionlimit(2*10**5+10) write = lambda x: sys.stdout.write(x+"\n") class UF: # unionfind def __init__(self, n): self.n = n self.parent = list(range(n)) self.size = [1] * n def root(self, i): inter = set() while self.parent[i]!=i: inter.add(i) i = self.parent[i] r = i for i in inter: self.parent[i] = r return r def connect(self, i, j): # 繋いだかどうかを返す ri = self.root(i) rj = self.root(j) if ri==rj: return False if self.size[ri]