Simple & Beginner Friendly Solution || 🌟 O(E) 🌟 || DSU || c++ | Java | python
IntuitionIn this problem there are 2 major observation:
-> If we use DSU(Disjoint Set Union). we can conclude in O(1) time that the query node are connected or
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
In this problem there are 2 major observation:
-> If we use DSU(Disjoint Set Union). we can conclude in O(1) time that the query node are connected or not.
-> We have to give the minimum possible AND.AND is of Non increasing nature.we can observe that as we AND more numbers Our final AND will either same or decreases But it never increase.
ie. For that we will AND whole connected component of that node if both the query nodes are connected else store -1 for that query.


# Approach
<!-- Describe your approach to solving the problem. -->
Make DSU of size n by using edges vector.After thet we will have each node parent as if nodes are in same component then parent will be same else parent will be different.

After that we will precompute AND for all nodes and store it in ands vector.
**One crucial thing is that we will store AND of component at component's main node(parent) index in ands vector.**

**Final step:** If parent of both query node is same then store AND of that component in ans vector.else store -1.

# Complexity
- Time complexity:  **O(E+Q)**
E : Size of edges vector
Q : Size of query vector


- Space complexity:**O(N)**
N : No. of nodes

# Code
```cpp []
class Solution {
public:

    class dsu{  
    public:
        vector<int> par;
        vector<int> rank;
        dsu(int n){
            rank.resize(n+1,1);
            par.resize(n+1);
            iota(par.begin(),par.end(),0);
        }
        int find_set(int v){
            if(v==par[v]) return v;
            return find_set(par[v]);//path compresion
        }

        void union_sets(int a, int b){
            a = find_set(a);//left tree
            b = find_set(b);//rigtht tree
            if(a!=b){
                if(rank[a] < rank[b]) swap(a,b);//iunion by sizes
                par[b] = a;
                rank[a] += rank[b];
            }
        }
    };

    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& query) {
        dsu ds(n);
        vector<int> ands(n+1,-1);

        for(auto it:edges){
            ds.union_sets(it[0],it[1]);
        }
        for(auto it:edges){
            if(ds.find_set(it[0])==ds.find_set(it[1])){
                int cur=ands[ds.find_set(it[0])];

                ands[ds.find_set(it[0])] = ( (cur==-1)? it[2] : (it[2]&cur));
            }
        }
        
        vector<int> ans;
        for(auto it:query){
            if(ds.find_set(it[0])==ds.find_set(it[1])){
                ans.push_back(ands[ds.find_set(it[0])]);
            }
            else ans.push_back(-1);
        }
        return ans;
    }
};
```
``` python []
from typing import List

class DSU:
    def __init__(self, n):
        self.par = list(range(n + 1))
        self.rank = [1] * (n + 1)

    def find_set(self, v):
        if v == self.par[v]:
            return v
        self.par[v] = self.find_set(self.par[v])  # Path compression
        return self.par[v]

    def union_sets(self, a, b):
        a = self.find_set(a)
        b = self.find_set(b)
        if a != b:
            if self.rank[a] < self.rank[b]:
                a, b = b, a
            self.par[b] = a
            self.rank[a] += self.rank[b]

class Solution:
    def minimumCost(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:
        ds = DSU(n)
        ands = [-1] * (n + 1)

        for u, v, w in edges:
            ds.union_sets(u, v)

        for u, v, w in edges:
            root = ds.find_set(u)
            cur = ands[root]
            ands[root] = w if cur == -1 else (cur & w)

        ans = []
        for u, v in query:
            if ds.find_set(u) == ds.find_set(v):
                ans.append(ands[ds.find_set(u)])
            else:
                ans.append(-1)

        return ans
```

``` java []
import java.util.*;

class Solution {
    class DSU {
        int[] par, rank;
        
        public DSU(int n) {
            par = new int[n + 1];
            rank = new int[n + 1];
            Arrays.fill(rank, 1);
            for (int i = 0; i <= n; i++) par[i] = i;
        }

        public int find_set(int v) {
            if (v == par[v]) return v;
            return par[v] = find_set(par[v]); // Path compression
        }

        public void union_sets(int a, int b) {
            a = find_set(a);
            b = find_set(b);
            if (a != b) {
                if (rank[a] < rank[b]) {
                    int temp = a;
                    a = b;
                    b = temp;
                }
                par[b] = a;
                rank[a] += rank[b];
            }
        }
    }

    public List<Integer> minimumCost(int n, int[][] edges, int[][] query) {
        DSU ds = new DSU(n);
        int[] ands = new int[n + 1];
        Arrays.fill(ands, -1);

        for (int[] it : edges) {
            ds.union_sets(it[0], it[1]);
        }

        for (int[] it : edges) {
            int root = ds.find_set(it[0]);
            int cur = ands[root];
            ands[root] = (cur == -1) ? it[2] : (cur & it[2]);
        }

        List<Integer> ans = new ArrayList<>();
        for (int[] it : query) {
            if (ds.find_set(it[0]) == ds.find_set(it[1])) {
                ans.add(ands[ds.find_set(it[0])]);
            } else {
                ans.add(-1);
            }
        }
        return ans;
    }
}
```


['Union Find', 'Graph', 'C++', 'Java', 'Python3']