class NaiveDSU:
    def __init__(self, n):
        # Initialize each element as its own parent (each in its own set)
        self.parent = list(range(n))

    def find(self, i):
        # Traverse up until the root is found
        while self.parent[i] != i:
            i = self.parent[i]
        return i

    def union(self, i, j):
        # Find the roots of i and j
        root_i = self.find(i)
        root_j = self.find(j)

        # If they are not already in the same set, merge them
        if root_i != root_j:
            self.parent[root_i] = root_j # Make root_j the parent of root_i
            return True # Successfully united
        return False # Already in the same set

# Example Usage: Naive DSU
print("--- Naive DSU Example ---")
n_naive = 5
dsu_naive = NaiveDSU(n_naive)

print(f"Initial state: {dsu_naive.parent}")
print(f"Find(0): {dsu_naive.find(0)}")
print(f"Find(3): {dsu_naive.find(3)}")

dsu_naive.union(0, 1) # Merge set of 0 and set of 1
print(f"After union(0, 1): {dsu_naive.parent}")
print(f"Find(0): {dsu_naive.find(0)}") # Should be same as Find(1)
print(f"Find(1): {dsu_naive.find(1)}")

dsu_naive.union(2, 3) # Merge set of 2 and set of 3
print(f"After union(2, 3): {dsu_naive.parent}")

dsu_naive.union(0, 2) # Merge set of 0 and set of 2 (which now includes 1 and 3)
print(f"After union(0, 2): {dsu_naive.parent}")
print(f"Are 1 and 3 connected? {dsu_naive.find(1) == dsu_naive.find(3)}")
print(f"Are 0 and 4 connected? {dsu_naive.find(0) == dsu_naive.find(4)}")

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        # For union by size/rank, we also need to store the size/rank of each set
        # Using size for simplicity and common practice. `size[i]` is only valid if `i` is a root.
        self.size = [1] * n 

    def find(self, i):
        if self.parent[i] == i:
            return i
        # Path compression: make i's parent the root directly
        self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def union(self, i, j):
        # We will implement union by size in the next section
        pass # Placeholder for now

# Example Usage: Path Compression (without full union implemented yet)
print("\n--- Path Compression Example (Find only) ---")
n_pc = 10
dsu_pc = DSU(n_pc)

# Manually create a long chain for demonstration
dsu_pc.parent[1] = 0
dsu_pc.parent[2] = 1
dsu_pc.parent[3] = 2
dsu_pc.parent[4] = 3

print(f"Initial parent state: {dsu_pc.parent}")
print(f"Finding root of 4: {dsu_pc.find(4)}") # This will compress the path
print(f"Parent state after find(4): {dsu_pc.parent}")
# Notice how parent[4], parent[3], parent[2], parent[1] all now point to 0 directly.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n # size[i] stores the size of the set if i is its root
        self.num_components = n # Track the number of disjoint sets

    def find(self, i):
        """
        Finds the representative (root) of the set containing element i,
        with path compression.
        """
        if self.parent[i] == i:
            return i
        self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def union(self, i, j):
        """
        Unites the sets containing elements i and j,
        using union by size.
        Returns True if a merge happened, False if they were already in the same set.
        """
        root_i = self.find(i)
        root_j = self.find(j)

        if root_i != root_j:
            # Union by size: attach smaller tree under root of larger tree
            if self.size[root_i] < self.size[root_j]:
                self.parent[root_i] = root_j
                self.size[root_j] += self.size[root_i]
            else:
                self.parent[root_j] = root_i
                self.size[root_i] += self.size[root_j]
            self.num_components -= 1 # One less component after successful merge
            return True
        return False # Elements already in the same set

    def is_connected(self, i, j):
        """
        Checks if elements i and j are in the same set.
        """
        return self.find(i) == self.find(j)

    def get_num_components(self):
        """
        Returns the current number of disjoint sets.
        """
        return self.num_components

    def get_set_size(self, i):
        """
        Returns the size of the set containing element i.
        """
        return self.size[self.find(i)]

# Example Usage: Optimized DSU
print("\n--- Optimized DSU Example ---")
num_elements = 7
dsu_opt = DSU(num_elements)

print(f"Initial state: {dsu_opt.parent}, Sizes: {dsu_opt.size}, Components: {dsu_opt.get_num_components()}")

dsu_opt.union(0, 1)
dsu_opt.union(1, 2) # Union(0,1) then Union(1,2) -> {0,1,2}
print(f"After union(0,1), union(1,2): {dsu_opt.parent}, Sizes: {dsu_opt.size}, Components: {dsu_opt.get_num_components()}")
print(f"Are 0 and 2 connected? {dsu_opt.is_connected(0, 2)}")

dsu_opt.union(3, 4)
dsu_opt.union(5, 6)
print(f"After union(3,4), union(5,6): {dsu_opt.parent}, Sizes: {dsu_opt.size}, Components: {dsu_opt.get_num_components()}")

print(f"Is 0 connected to 3? {dsu_opt.is_connected(0, 3)}")

dsu_opt.union(2, 5) # Union set {0,1,2} with set {5,6}
print(f"After union(2,5): {dsu_opt.parent}, Sizes: {dsu_opt.size}, Components: {dsu_opt.get_num_components()}")
print(f"Is 0 connected to 6? {dsu_opt.is_connected(0, 6)}")
print(f"Size of set containing 0: {dsu_opt.get_set_size(0)}")
print(f"Size of set containing 3: {dsu_opt.get_set_size(3)}")

# Assuming the DSU class from above is defined

def count_connected_components(n_vertices, edges):
    dsu = DSU(n_vertices)
    for u, v in edges:
        dsu.union(u, v)
    return dsu.get_num_components()

print("\n--- Connected Components Example ---")
num_vertices = 7
graph_edges = [
    (0, 1),
    (1, 2),
    (3, 4),
    (0, 2), # Redundant, but union handles it
    (5, 6)
]

components = count_connected_components(num_vertices, graph_edges)
print(f"Number of connected components: {components}")

# Example 2: More complex graph
num_vertices_2 = 9
graph_edges_2 = [
    (0, 1), (1, 2),
    (3, 4), (4, 5), (5, 3), # A cycle
    (6, 7)
]
components_2 = count_connected_components(num_vertices_2, graph_edges_2)
print(f"Number of connected components (complex graph): {components_2}")

# Let's also see the groups formed
dsu_graph_groups = DSU(num_vertices_2)
for u,v in graph_edges_2:
    dsu_graph_groups.union(u,v)

groups = {}
for i in range(num_vertices_2):
    root = dsu_graph_groups.find(i)
    if root not in groups:
        groups[root] = []
    groups[root].append(i)

print("Groups formed (elements with same root):")
for root, elements in groups.items():
    print(f"  Root {root}: {elements}")

# Assuming the DSU class from above is defined

def kruskal_mst(n_vertices, edges):
    # Edges format: (weight, u, v)
    edges.sort() # Sort by weight

    dsu = DSU(n_vertices)
    mst_cost = 0
    mst_edges = []
    edges_count = 0

    for weight, u, v in edges:
        if dsu.union(u, v): # If union successful (no cycle formed)
            mst_cost += weight
            mst_edges.append((u, v, weight))
            edges_count += 1
            if edges_count == n_vertices - 1: # MST has N-1 edges
                break
    return mst_cost, mst_edges

print("\n--- Kruskal's MST Example ---")
num_vertices_mst = 6
edges_mst = [
    (1, 0, 1),
    (5, 0, 2),
    (10, 1, 2),
    (2, 1, 3),
    (4, 2, 4),
    (3, 3, 4),
    (6, 4, 5)
]

cost, edges = kruskal_mst(num_vertices_mst, edges_mst)
print(f"Minimum Spanning Tree Cost: {cost}")
print("MST Edges:")
for u, v, w in edges:
    print(f"  ({u}, {v}) - Weight: {w}")

# Assuming the DSU class from above is defined

def num_islands(grid):
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])
    # Map (r, c) to a 1D index: r * cols + c
    dsu = DSU(rows * cols)
    
    # Keep track of roots that are actually land cells
    land_roots = set()

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1': # If it's land
                current_idx = r * cols + c
                land_roots.add(dsu.find(current_idx)) # Add its root (initially itself)
                
                # Check neighbors (right and down, to avoid double counting and going out of bounds)
                # Up and Left neighbors would have already processed this cell.
                # Only need to connect to already processed land cells or newly encountered ones.
                # A simpler approach is to check all 4 neighbors and let union handle it.
                
                # Check right neighbor
                if c + 1 < cols and grid[r][c+1] == '1':
                    dsu.union(current_idx, r * cols + (c + 1))
                # Check down neighbor
                if r + 1 < rows and grid[r+1][c] == '1':
                    dsu.union(current_idx, (r + 1) * cols + c)
    
    # After all unions, iterate through all land cells again to find their final roots
    # and count distinct roots.
    final_island_roots = set()
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                final_island_roots.add(dsu.find(r * cols + c))
                
    return len(final_island_roots)

print("\n--- Counting Islands Example ---")
grid1 = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
print(f"Number of islands in Grid 1: {num_islands(grid1)}")

grid2 = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
print(f"Number of islands in Grid 2: {num_islands(grid2)}")