Two methods: DFS / Union-Find (Python/Java/C++/Go)
Discussion:\n\n- If $s=t$, no movement is needed, the answer is $0$.\n- If $s$ and $t$ are not in the same connected component, the answer is $-1$.\n- If $s$ an
Discussion:\n\n- If $s=t$, no movement is needed, the answer is $0$.\n- If $s$ and $t$ are not in the same connected component, the answer is $-1$.\n- If $s$ and $t$ are in the same connected component. Since the property of AND is that the more numbers ANDed, the smaller the result. With the condition of being able to repeat edges, the optimal solution is to traverse all edges within the connected component where $s$ lies.\nSo we need to know which connected component $s$ and $t$ belong to, and what the AND of edge weights is within the connected component.\n\nThis can be implemented using either DFS or Union Find.\n\n## DFS\n\n```py [sol-Python3]\nclass Solution:\n    def minimumCost(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:\n        g = [[] for _ in range(n)]\n        for x, y, w in edges:\n            g[x].append((y, w))\n            g[y].append((x, w))\n\n        def dfs(x: int) -> int:\n            and_ = -1\n            ids[x] = len(cc_and)\n            for y, w in g[x]:\n                and_ &= w\n                if ids[y] < 0:\n                    and_ &= dfs(y)\n            return and_\n\n        ids = [-1] * n\n        cc_and = []\n        for i in range(n):\n            if ids[i] < 0:\n                cc_and.append(dfs(i))\n\n        return [0 if s == t else -1 if ids[s] != ids[t] else cc_and[ids[s]]\n                for s, t in query]\n```\n\n```java [sol-Java]\nclass Solution {\n    public int[] minimumCost(int n, int[][] edges, int[][] query) {\n        List<int[]>[] g = new ArrayList[n];\n        Arrays.setAll(g, i -> new ArrayList<>());\n        for (int[] e : edges) {\n            int x = e[0], y = e[1], w = e[2];\n            g[x].add(new int[]{y, w});\n            g[y].add(new int[]{x, w});\n        }\n\n        int[] ids = new int[n];\n        Arrays.fill(ids, -1);\n        List<Integer> ccAnd = new ArrayList<>();\n        for (int i = 0; i < n; i++) {\n            if (ids[i] < 0) {\n                ccAnd.add(dfs(i, ccAnd.size(), g, ids));\n            }\n        }\n\n        int[] ans = new int[query.length];\n        for (int i = 0; i < query.length; i++) {\n            int s = query[i][0], t = query[i][1];\n            ans[i] = s == t ? 0 : ids[s] != ids[t] ? -1 : ccAnd.get(ids[s]);\n        }\n        return ans;\n    }\n\n    private int dfs(int x, int curId, List<int[]>[] g, int[] ids) {\n        ids[x] = curId;\n        int and = -1;\n        for (int[] e : g[x]) {\n            and &= e[1];\n            if (ids[e[0]] < 0) {\n                and &= dfs(e[0], curId, g, ids);\n            }\n        }\n        return and;\n    }\n}\n```\n\n```cpp [sol-C++]\nclass Solution {\n    vector<vector<pair<int, int>>> g;\n    vector<int> cc_and, ids;\n\n    int dfs(int x) {\n        ids[x] = cc_and.size(); \n        int and_ = -1;\n        for (auto &[y, w]: g[x]) {\n            and_ &= w;\n            if (ids[y] < 0) { \n                and_ &= dfs(y);\n            }\n        }\n        return and_;\n    }\n\npublic:\n    vector<int> minimumCost(int n, vector<vector<int>> &edges, vector<vector<int>> &query) {\n        g.resize(n);\n        for (auto &e: edges) {\n            int x = e[0], y = e[1], w = e[2];\n            g[x].emplace_back(y, w);\n            g[y].emplace_back(x, w);\n        }\n\n        ids.resize(n, -1); \n        for (int i = 0; i < n; i++) {\n            if (ids[i] < 0) { \n                cc_and.push_back(dfs(i)); \n            }\n        }\n\n        vector<int> ans;\n        ans.reserve(query.size());\n        for (auto &q: query) {\n            int s = q[0], t = q[1];\n            ans.push_back(s == t ? 0 : ids[s] != ids[t] ? -1 : cc_and[ids[s]]);\n        }\n        return ans;\n    }\n};\n```\n\n```go [sol-Go]\nfunc minimumCost(n int, edges, query [][]int) []int {\n\ttype edge struct{ to, w int }\n\tg := make([][]edge, n)\n\tfor _, e := range edges {\n\t\tx, y, w := e[0], e[1], e[2]\n\t\tg[x] = append(g[x], edge{y, w})\n\t\tg[y] = append(g[y], edge{x, w})\n\t}\n\n\tids := make([]int, n) \n\tfor i := range ids {\n\t\tids[i] = -1\n\t}\n\tccAnd := []int{} \n\tvar dfs func(int) int\n\tdfs = func(x int) int {\n\t\tids[x] = len(ccAnd) \n\t\tand := -1\n\t\tfor _, e := range g[x] {\n\t\t\tand &= e.w\n\t\t\tif ids[e.to] < 0 {\n\t\t\t\tand &= dfs(e.to)\n\t\t\t}\n\t\t}\n\t\treturn and\n\t}\n\tfor i, id := range ids {\n\t\tif id < 0 { // \u6CA1\u6709\u8BBF\u95EE\u8FC7\n\t\t\tccAnd = append(ccAnd, dfs(i))\n\t\t}\n\t}\n\n\tans := make([]int, len(query))\n\tfor i, q := range query {\n\t\ts, t := q[0], q[1]\n\t\tif s == t {\n\t\t\tcontinue\n\t\t}\n\t\tif ids[s] != ids[t] {\n\t\t\tans[i] = -1\n\t\t} else {\n\t\t\tans[i] = ccAnd[ids[s]]\n\t\t}\n\t}\n\treturn ans\n}\n```\n\n#### Complexity Analysis\n\n- **Time complexity**: $\\mathcal{O}(n+m+q)$, where $m$ is the length of $\\textit{edges}$, and $q$ is the length of $\\textit{query}$.\n- **Space complexity**: $\\mathcal{O}(n+m)$. The return value is not included.\n\n## Union Find\n\n```py [sol-Python3]\nclass Solution:\n    def minimumCost(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:\n        fa = list(range(n))\n        and_ = [-1] * n\n\n        def find(x: int) -> int:\n            if fa[x] != x:\n                fa[x] = find(fa[x])\n            return fa[x]\n\n        for x, y, w in edges:\n            x = find(x)\n            y = find(y)\n            and_[y] &= w\n            if x != y:\n                and_[y] &= and_[x]\n                fa[x] = y\n\n        return [0 if s == t else -1 if find(s) != find(t) else and_[find(s)]\n                for s, t in query]\n```\n\n```java [sol-Java]\nclass Solution {\n    public int[] minimumCost(int n, int[][] edges, int[][] query) {\n        int[] fa = new int[n];\n        for (int i = 0; i < n; i++) {\n            fa[i] = i;\n        }\n        int[] and_ = new int[n];\n        Arrays.fill(and_, -1);\n\n        for (int[] e : edges) {\n            int x = find(e[0], fa);\n            int y = find(e[1], fa);\n            and_[y] &= e[2];\n            if (x != y) {\n                and_[y] &= and_[x];\n                fa[x] = y;\n            }\n        }\n\n        int[] ans = new int[query.length];\n        for (int i = 0; i < query.length; i++) {\n            int s = query[i][0], t = query[i][1];\n            ans[i] = s == t ? 0 : find(s, fa) != find(t, fa) ? -1 : and_[find(s, fa)];\n        }\n        return ans;\n    }\n\n    private int find(int x, int[] fa) {\n        if (fa[x] != x) {\n            fa[x] = find(fa[x], fa);\n        }\n        return fa[x];\n    }\n}\n```\n\n```cpp [sol-C++]\nclass Solution {\n    vector<int> fa, and_;\n\n    int find(int x) {\n        if (fa[x] != x) {\n            fa[x] = find(fa[x]);\n        }\n        return fa[x];\n    };\n\npublic:\n    vector<int> minimumCost(int n, vector<vector<int>> &edges, vector<vector<int>> &query) {\n        fa.resize(n);\n        iota(fa.begin(), fa.end(), 0);\n        and_.resize(n, -1);\n        for (auto &e: edges) {\n            int x = find(e[0]);\n            int y = find(e[1]);\n            and_[y] &= e[2];\n            if (x != y) {\n                and_[y] &= and_[x];\n                fa[x] = y;\n            }\n        }\n\n        vector<int> ans;\n        ans.reserve(query.size()); \n        for (auto &q: query) {\n            int s = q[0], t = q[1];\n            ans.push_back(s == t ? 0 : find(s) != find(t) ? -1 : and_[find(s)]);\n        }\n        return ans;\n    }\n};\n```\n\n```go [sol-Go]\nfunc minimumCost(n int, edges, query [][]int) []int {\n\tfa := make([]int, n)\n\tand := make([]int, n)\n\tfor i := range fa {\n\t\tfa[i] = i\n\t\tand[i] = -1\n\t}\n\tvar find func(int) int\n\tfind = func(x int) int {\n\t\tif fa[x] != x {\n\t\t\tfa[x] = find(fa[x])\n\t\t}\n\t\treturn fa[x]\n\t}\n\n\tfor _, e := range edges {\n\t\tx, y := find(e[0]), find(e[1])\n\t\tand[y] &= e[2]\n\t\tif x != y {\n\t\t\tand[y] &= and[x]\n\t\t\tfa[x] = y\n\t\t}\n\t}\n\n\tans := make([]int, len(query))\n\tfor i, q := range query {\n\t\ts, t := q[0], q[1]\n\t\tif s == t {\n\t\t\tcontinue\n\t\t}\n\t\tif find(s) != find(t) {\n\t\t\tans[i] = -1\n\t\t} else {\n\t\t\tans[i] = and[find(s)]\n\t\t}\n\t}\n\treturn ans\n}\n```\n\n#### Complexity Analysis\n\n- **Time complexity**: $\\mathcal{O}((n+m+q)\\log n)$, where $m$ is the length of $\\textit{edges}$, and $q$ is the length of $\\textit{query}$.\n- **Space complexity**: $\\mathcal{O}(n+m)$. The return value is not included.\n
['Depth-First Search', 'Union Find', 'C++', 'Java', 'Go', 'Python3']