1/**
2 * Union-Find (Disjoint Set Union) data structure with path compression and union by size
3 */
4class UnionFind {
5    private final int[] parent;      // parent[i] stores the parent of node i
6    private final int[] componentSize; // componentSize[i] stores the size of component with root i
7
8    /**
9     * Initialize Union-Find structure with n nodes (0 to n-1)
10     * Initially, each node is its own parent (separate component)
11     */
12    public UnionFind(int n) {
13        parent = new int[n];
14        componentSize = new int[n];
15        for (int i = 0; i < n; i++) {
16            parent[i] = i;           // Each node is initially its own parent
17            componentSize[i] = 1;    // Each component initially has size 1
18        }
19    }
20
21    /**
22     * Find the root of the component containing node x
23     * Uses path compression to optimize future queries
24     */
25    public int find(int x) {
26        if (parent[x] != x) {
27            parent[x] = find(parent[x]); // Path compression: directly connect x to root
28        }
29        return parent[x];
30    }
31
32    /**
33     * Union two components containing nodes a and b
34     * Uses union by size to keep the tree balanced
35     * Returns true if union was performed, false if already in same component
36     */
37    public boolean union(int a, int b) {
38        int rootA = find(a);
39        int rootB = find(b);
40      
41        // Already in the same component
42        if (rootA == rootB) {
43            return false;
44        }
45      
46        // Union by size: attach smaller tree to larger tree
47        if (componentSize[rootA] > componentSize[rootB]) {
48            parent[rootB] = rootA;
49            componentSize[rootA] += componentSize[rootB];
50        } else {
51            parent[rootA] = rootB;
52            componentSize[rootB] += componentSize[rootA];
53        }
54        return true;
55    }
56
57    /**
58     * Get the size of the component containing node x
59     */
60    public int size(int x) {
61        return componentSize[find(x)];
62    }
63}
64
65/**
66 * Solution for finding minimum cost paths in a graph with bitwise AND edge weights
67 */
68class Solution {
69    private UnionFind unionFind;
70    private int[] componentMinCost; // Stores the bitwise AND of all edges in each component
71
72    /**
73     * Calculate minimum cost for each query
74     * @param n Number of nodes in the graph
75     * @param edges Array of edges where each edge is [from, to, weight]
76     * @param query Array of queries where each query is [start, end]
77     * @return Array of minimum costs for each query
78     */
79    public int[] minimumCost(int n, int[][] edges, int[][] query) {
80        // Initialize Union-Find and build connected components
81        unionFind = new UnionFind(n);
82        for (int[] edge : edges) {
83            unionFind.union(edge[0], edge[1]);
84        }
85      
86        // Initialize component costs with -1 (all bits set to 1)
87        componentMinCost = new int[n];
88        Arrays.fill(componentMinCost, -1);
89      
90        // Calculate bitwise AND of all edge weights for each component
91        for (int[] edge : edges) {
92            int componentRoot = unionFind.find(edge[0]);
93            componentMinCost[componentRoot] &= edge[2]; // Bitwise AND with edge weight
94        }
95      
96        // Process each query
97        int queryCount = query.length;
98        int[] result = new int[queryCount];
99        for (int i = 0; i < queryCount; i++) {
100            int start = query[i][0];
101            int end = query[i][1];
102            result[i] = calculateMinimumCost(start, end);
103        }
104      
105        return result;
106    }
107
108    /**
109     * Calculate minimum cost from node u to node v
110     * @param u Start node
111     * @param v End node
112     * @return 0 if u equals v, component's minimum cost if connected, -1 if not connected
113     */
114    private int calculateMinimumCost(int u, int v) {
115        // Same node: cost is 0
116        if (u == v) {
117            return 0;
118        }
119      
120        // Check if nodes are in the same component
121        int rootU = unionFind.find(u);
122        int rootV = unionFind.find(v);
123      
124        // If in same component, return the component's minimum cost
125        // Otherwise, return -1 (not connected)
126        return rootU == rootV ? componentMinCost[rootU] : -1;
127    }
128}
129

1class UnionFind {
2public:
3    // Initialize Union-Find structure with n elements
4    UnionFind(int n) {
5        parent = vector<int>(n);
6        componentSize = vector<int>(n, 1);
7        // Initialize each element as its own parent (self-loop)
8        iota(parent.begin(), parent.end(), 0);
9    }
10
11    // Unite two elements into the same component
12    // Returns true if they were in different components, false otherwise
13    bool unite(int a, int b) {
14        int rootA = find(a);
15        int rootB = find(b);
16      
17        // Already in the same component
18        if (rootA == rootB) {
19            return false;
20        }
21      
22        // Union by size: attach smaller tree under root of larger tree
23        if (componentSize[rootA] > componentSize[rootB]) {
24            parent[rootB] = rootA;
25            componentSize[rootA] += componentSize[rootB];
26        } else {
27            parent[rootA] = rootB;
28            componentSize[rootB] += componentSize[rootA];
29        }
30        return true;
31    }
32
33    // Find the root of the component containing element x
34    // Uses path compression for optimization
35    int find(int x) {
36        if (parent[x] != x) {
37            parent[x] = find(parent[x]);  // Path compression
38        }
39        return parent[x];
40    }
41
42    // Get the size of the component containing element x
43    int getSize(int x) {
44        return componentSize[find(x)];
45    }
46
47private:
48    vector<int> parent;        // Parent array for Union-Find
49    vector<int> componentSize; // Size of each component
50};
51
52class Solution {
53public:
54    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& query) {
55        // Initialize component weights array with all bits set (-1)
56        componentWeights = vector<int>(n, -1);
57        unionFind = new UnionFind(n);
58      
59        // Build connected components by uniting nodes connected by edges
60        for (auto& edge : edges) {
61            unionFind->unite(edge[0], edge[1]);
62        }
63      
64        // Calculate bitwise AND of all edge weights in each component
65        for (auto& edge : edges) {
66            int componentRoot = unionFind->find(edge[0]);
67            componentWeights[componentRoot] &= edge[2];
68        }
69      
70        // Process queries and build result array
71        vector<int> result;
72        for (auto& q : query) {
73            result.push_back(calculateQueryCost(q[0], q[1]));
74        }
75      
76        return result;
77    }
78
79private:
80    UnionFind* unionFind;           // Union-Find data structure
81    vector<int> componentWeights;   // Bitwise AND of all edge weights in each component
82  
83    // Calculate the cost for a query from node u to node v
84    int calculateQueryCost(int u, int v) {
85        // Same node, cost is 0
86        if (u == v) {
87            return 0;
88        }
89      
90        // Find the root components of both nodes
91        int rootU = unionFind->find(u);
92        int rootV = unionFind->find(v);
93      
94        // If in same component, return the component's weight
95        // Otherwise, nodes are not connected, return -1
96        return (rootU == rootV) ? componentWeights[rootU] : -1;
97    }
98};
99

1// Parent array for Union-Find data structure
2let parent: number[];
3// Size array to track component sizes for union by rank optimization
4let componentSize: number[];
5
6/**
7 * Initialize Union-Find data structure
8 * @param n - Number of nodes
9 */
10function initializeUnionFind(n: number): void {
11    // Each node is initially its own parent
12    parent = Array(n).fill(0).map((_, index) => index);
13    // Each component initially has size 1
14    componentSize = Array(n).fill(1);
15}
16
17/**
18 * Find the root parent of a node with path compression
19 * @param x - Node to find root for
20 * @returns Root parent of the node
21 */
22function find(x: number): number {
23    // Path compression: make all nodes point directly to root
24    if (parent[x] !== x) {
25        parent[x] = find(parent[x]);
26    }
27    return parent[x];
28}
29
30/**
31 * Unite two components using union by size
32 * @param a - First node
33 * @param b - Second node
34 * @returns true if union was performed, false if already in same component
35 */
36function union(a: number, b: number): boolean {
37    // Find roots of both nodes
38    const rootA = find(a);
39    const rootB = find(b);
40  
41    // Already in same component
42    if (rootA === rootB) {
43        return false;
44    }
45  
46    // Union by size: attach smaller tree under larger tree
47    if (componentSize[rootA] > componentSize[rootB]) {
48        parent[rootB] = rootA;
49        componentSize[rootA] += componentSize[rootB];
50    } else {
51        parent[rootA] = rootB;
52        componentSize[rootB] += componentSize[rootA];
53    }
54  
55    return true;
56}
57
58/**
59 * Get the size of the component containing node x
60 * @param x - Node to check
61 * @returns Size of the component
62 */
63function getSize(x: number): number {
64    return componentSize[find(x)];
65}
66
67/**
68 * Find minimum cost path between nodes in a graph
69 * @param n - Number of nodes
70 * @param edges - Array of edges [u, v, weight]
71 * @param query - Array of queries [start, end]
72 * @returns Array of minimum costs for each query
73 */
74function minimumCost(n: number, edges: number[][], query: number[][]): number[] {
75    // Initialize Union-Find structure
76    initializeUnionFind(n);
77  
78    // Array to store bitwise AND result for each component
79    const componentWeight: number[] = Array(n).fill(-1);
80  
81    // Build connected components by unioning all edges
82    for (const [nodeU, nodeV, _] of edges) {
83        union(nodeU, nodeV);
84    }
85  
86    // Calculate bitwise AND of all edge weights in each component
87    for (const [nodeU, _, weight] of edges) {
88        const rootNode = find(nodeU);
89        componentWeight[rootNode] &= weight;
90    }
91  
92    /**
93     * Helper function to find minimum cost between two nodes
94     * @param startNode - Starting node
95     * @param endNode - Ending node
96     * @returns Minimum cost or -1 if not connected
97     */
98    const findMinimumCost = (startNode: number, endNode: number): number => {
99        // Same node has zero cost
100        if (startNode === endNode) {
101            return 0;
102        }
103      
104        // Check if nodes are in same component
105        const rootStart = find(startNode);
106        const rootEnd = find(endNode);
107      
108        // If in same component, return component's weight, else -1
109        return rootStart === rootEnd ? componentWeight[rootStart] : -1;
110    };
111  
112    // Process each query and return results
113    return query.map(([startNode, endNode]) => findMinimumCost(startNode, endNode));
114}
115