
from typing import List


class UnionFind:
    def __init__(self, N):
        self.node2par = {i: i for i in range(1, N + 1)}
        self.rank = {i: 0 for i in range(1, N + 1)}

    def find_par(self, x):
        if self.node2par[x] != x:
            x = self.find_par(self.node2par[x])