1
class Solution:
2
    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:
3

4
        gcdset = [set() for i in range(51)]
5
        for i in range(1, 51):
6
            for j in range(1, 51):
7
                if math.gcd(i, j) == 1:
8
                    gcdset[i].add(j)
9
                    gcdset[j].add(i)
10

11
        graph = defaultdict(list)
12
        for v1, v2 in edges:
13
            graph[v1].append(v2)
14
            graph[v2].append(v1)
15

16
        ans = [-1] * len(nums)
17
        q = [[0, {}]]
18
        seen = set([0])
19
        depth = 0
20
        while q:
21
            temp = []
22
            for node, ancestors in q:
23
                index_depth = (-1, -1)
24
                for anc in list(ancestors.keys()):
25
                    if anc in gcdset[nums[node]]:
26
                        index, d = ancestors[anc]
27
                        if d > index_depth[1]:
28
                            index_depth = (index, d)
29
                ans[node] = index_depth[0]
30

31
                copy = ancestors.copy()
32
                copy[nums[node]] = (node, depth)
33

34
                for child in graph[node]:
35
                    if child not in seen:
36
                        seen.add(child)
37
                        temp.append([child, copy])
38
            q = temp
39
            depth += 1
40
        return ans