from typing import List
# 我们使用并查集来做这道题，一共N台电脑的话，至少需要n-1根线。
# 并查集模板
class UnionFind:
    def __init__(self):
        #记录每一个节点的父节点
        self.size = 0
        self.father = {}
    def find(self,x):
        """寻找根节点，路径压缩"""
        root = x
        while self.father[root] != None:
            root = self.father[root]
        while x != root:
            oraginal_father = self.father[x]
            self.father[x] = root
            x = oraginal_father
        return root
    def merge(self,x,y):
        """合并两个并查集"""
        root_x,root_y = self.find(x),self.find(y)
        if root_x != root_y:
            self.father[root_y] = x
            self.size -= 1

    def is_connected(self,x,y):
        """判断两个节点是否相连"""
        return self.find(x) == self.find(y)
    def add(self,x):
        """添加新节点"""
        if x not in self.father:
            self.father[x] = None
        self.size += 1
class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        # 首先判断是否满足所有电脑都相连的条件。
        if len(connections) < n - 1:
            return -1
        # 定义一个并查集。
        res = UnionFind()
        # 将所有电脑添加到并查集中。
        for i in range(n):
            res.add(i)
        # 判断两个电脑是否相连，也就是是否同属于一个根节点。
        # 如果不是的话，那么我们就将这两个电脑相连。
        # 最后就可以求出来冗余的连线，然后拨动他们，就可以将所有的电脑相连了。
        for nums in connections:
            if not res.is_connected(nums[0],nums[1]):
                res.merge(nums[0],nums[1])
        # 因为size是总的电脑数，跟连线数不一样。
        return res.size - 1

# A = Solution()
# print(A.makeConnected(4,[[0,1],[0,2],[1,2]]))