Beautiful Union Find Solution 🌸
IntuitionWe have following property for AND opreator: if we apply AND for all weights of edges in a connectivity component, we will get minimal possible value (
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
We have following property for `AND` opreator: if we apply `AND` for all weights of edges in a connectivity component, we will get minimal possible value (since $x & y & z \leq x & y$). So, all we need is to compute `AND` of weights of all edges per connectivity component efficently.
We will try to use Union Find structure with some modification for this task

# Approach
<!-- Describe your approach to solving the problem. -->
See code below

# Complexity
- Time complexity: $$O(\alpha(n))$$,  where $\alpha(n)$ is the inverse Ackermann function 
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: $$O(n)$$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```python []
class UnionFind:
    def __init__(self, n: int):
        self.root = list(range(n + 1))
        self.size = [1] * (n + 1)
        self.components = [2 ** 21 - 1] * (n + 1)

    def find(self, x: int) -> int:
        if self.root[x] == x:
            return x
        self.root[x] = self.find(self.root[x])
        return self.root[x]

    def union(self, x: int, y: int, w: int) -> int:
        x = self.find(x)
        y = self.find(y)
        if x == y:
            self.components[x] &= w
            return 0

        if self.size[x] > self.size[y]:
            self.size[x] += self.size[y]
            self.components[x] &= self.components[y] & w
            self.root[y] = x
        else:
            self.size[y] += self.size[x]
            self.components[y] &= self.components[x] & w
            self.root[x] = y

        return 1

    def are_connected(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)


class Solution:
    def minimumCost(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:
        uf = UnionFind(n)
        for u, v, w in edges:
            uf.union(u, v, w)
        
        answer = []
        for s, t in query:
            if uf.are_connected(s, t):
                answer.append(uf.components[uf.find(s)])
            else:
                answer.append(-1)
        
        return answer


        
```
```rust []
struct UnionFind {
    root: Vec<usize>,
    size: Vec<i32>,
    pub components: Vec<i32>,
}


impl UnionFind {
    pub fn new(n: usize) -> Self {
        UnionFind {
            root: (0..=n + 1).collect(),
            size: vec![1; n + 1],
            components: vec![2_i32.pow(21) - 1; n + 1],
        }
    }

    pub fn find(&mut self, x: usize) -> usize {
        if self.root[x] == x { return x }
        self.root[x] = self.find(self.root[x]);
        self.root[x]
    }

    pub fn union(&mut self, mut x: usize, mut y: usize, w: i32) -> bool {
        let x = self.find(x);
        let y = self.find(y);

        if x == y {
            self.components[x] &= w;
            return false
        }

        if self.size[x] > self.size[y] {
            self.size[x] += self.size[y];
            self.components[x] &= self.components[y] & w;
            self.root[y] = x
        } else {
            self.size[y] += self.size[x];
            self.components[y] &= self.components[x] & w;
            self.root[x] = y
        }

        true
    }

    pub fn are_connected(&mut self, x: usize, y: usize) -> bool {
        self.find(x) == self.find(y)
    }
}

impl Solution {
    pub fn minimum_cost(n: i32, edges: Vec<Vec<i32>>, query: Vec<Vec<i32>>) -> Vec<i32> {
        let mut uf = UnionFind::new(n as usize);
        for edge in edges.iter() {
            let (u, v, w) = (edge[0] as usize, edge[1] as usize, edge[2]);
            uf.union(u, v, w);
        }
            
        let mut answer = vec![-1; query.len()];
        for (i, q) in query.iter().enumerate() {
            let (s, t) = (q[0] as usize, q[1] as usize);
            if uf.are_connected(s, t) {
                let root = uf.find(s);
                answer[i] = uf.components[root] 
            }
                
        }
        
        answer
    }
}
```
['Union Find', 'Python3', 'Rust']