1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
package index
var prime = make([][]bool, 0)
func getCoprimes(nums []int, edges [][]int) []int {	var edge = make([][]int, len(nums))
	for i := range edge {		edge[i] = make([]int, 0)	}	for _, e := range edges {		a, b := e[0], e[1]		edge[a] = append(edge[a], b)		edge[b] = append(edge[b], a)	}	if len(prime) == 0 {		for i := 0; i < 51; i++ {			prime = append(prime, make([]bool, 51))		}		for i := 0; i < 51; i++ {			for j := i; j < 51; j++ {				prime[j][i] = greatestCommonDivisor(i, j) == 1				prime[i][j] = prime[j][i]			}		}	}
	var set = make(map[int]bool, 0)	for _, n := range nums {		set[n] = true	}	var visited = make(map[int]bool, 0)	var currents = make([][][]int, 51)	for i := 0; i < 51; i++ {		currents[i] = make([][]int, 0)	}
	var results = make([]int, len(nums))	var dfs func(node, depth int)	dfs = func(node, depth int) {		if visited[node] {			return		}		visited[node] = true		var value = nums[node]		var ans = []int{-1, -1}		for i := range set {			if len(currents[i]) > 0 && prime[value][i] {				var get = currents[i][len(currents[i])-1]				if get[1] > ans[1] {					ans = get				}			}		}		results[node] = ans[0]
		for _, child := range edge[node] {			currents[value] = append(currents[value], []int{node, depth})
			dfs(child, depth+1)			currents[value] = currents[value][0 : len(currents[value])-1]		}	}	dfs(0, 0)
	return results}
func greatestCommonDivisor(a int, b int) int {	for b != 0 {		return greatestCommonDivisor(b, a%b)	}	return a}