<p>There is a tree (i.e.,&nbsp;a connected, undirected graph that has no cycles) consisting of <code>n</code> nodes numbered from <code>0</code> to <code>n - 1</code> and exactly <code>n - 1</code> edges. Each node has a value associated with it, and the <strong>root</strong> of the tree is node <code>0</code>.</p>

<p>To represent this tree, you are given an integer array <code>nums</code> and a 2D array <code>edges</code>. Each <code>nums[i]</code> represents the <code>i<sup>th</sup></code> node&#39;s value, and each <code>edges[j] = [u<sub>j</sub>, v<sub>j</sub>]</code> represents an edge between nodes <code>u<sub>j</sub></code> and <code>v<sub>j</sub></code> in the tree.</p>

<p>Two values <code>x</code> and <code>y</code> are <strong>coprime</strong> if <code>gcd(x, y) == 1</code> where <code>gcd(x, y)</code> is the <strong>greatest common divisor</strong> of <code>x</code> and <code>y</code>.</p>

<p>An ancestor of a node <code>i</code> is any other node on the shortest path from node <code>i</code> to the <strong>root</strong>. A node is <strong>not </strong>considered an ancestor of itself.</p>

<p>Return <em>an array </em><code>ans</code><em> of size </em><code>n</code>, <em>where </em><code>ans[i]</code><em> is the closest ancestor to node </em><code>i</code><em> such that </em><code>nums[i]</code> <em>and </em><code>nums[ans[i]]</code> are <strong>coprime</strong>, or <code>-1</code><em> if there is no such ancestor</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2021/01/06/untitled-diagram.png" style="width: 191px; height: 281px;" /></strong></p>

<pre>
<strong>Input:</strong> nums = [2,3,3,2], edges = [[0,1],[1,2],[1,3]]
<strong>Output:</strong> [-1,0,0,1]
<strong>Explanation:</strong> In the above figure, each node&#39;s value is in parentheses.
- Node 0 has no coprime ancestors.
- Node 1 has only one ancestor, node 0. Their values are coprime (gcd(2,3) == 1).
- Node 2 has two ancestors, nodes 1 and 0. Node 1&#39;s value is not coprime (gcd(3,3) == 3), but node 0&#39;s
  value is (gcd(2,3) == 1), so node 0 is the closest valid ancestor.
- Node 3 has two ancestors, nodes 1 and 0. It is coprime with node 1 (gcd(3,2) == 1), so node 1 is its
  closest valid ancestor.
</pre>

<p><strong class="example">Example 2:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2021/01/06/untitled-diagram1.png" style="width: 441px; height: 291px;" /></p>

<pre>
<strong>Input:</strong> nums = [5,6,10,2,3,6,15], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]
<strong>Output:</strong> [-1,0,-1,0,0,0,-1]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>nums.length == n</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 50</code></li>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>edges.length == n - 1</code></li>
	<li><code>edges[j].length == 2</code></li>
	<li><code>0 &lt;= u<sub>j</sub>, v<sub>j</sub> &lt; n</code></li>
	<li><code>u<sub>j</sub> != v<sub>j</sub></code></li>
</ul>

class Solution:
    # set up with the initial size related to the problem 
    def __init__(self, set_size=50) : 
        self.gcd_set_size = set_size
        self.build_gcd_set()

    # get the gcd set built in a functional manner 
    def build_gcd_set(self) : 
        # build enough sets in range of size + 1 to account for including the final set size limit 
        self.gcd_set = [set() for _ in range(self.gcd_set_size+1)]
        # loop over set size space -> takes O(set size * set size) -> may be expensive for VERY large sets 
        for i in range(1, self.gcd_set_size + 1) : 
            for j in range(1, self.gcd_set_size+1) : 
                # use gcd, may be expensive for very large numbers -> consider lookup memoize version? 
                if math.gcd(i, j) == 1 : 
                    # if coprime, mark as needed 
                    self.gcd_set[i].add(j)
                    self.gcd_set[j].add(i)
    
    # not used for problem but good to include functionality 
    def alter_set_size(self, new_size) : 
        self.gcd_set_size = new_size 
        self.build_gcd_set()

    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:
        # get length of nums 
        nL = len(nums)
        # set up graph as a list of lists of length nL 
        graph = [[] for _ in range(nL)]
        # for src, dst in edges 
        for src, dst in edges : 
            # graph at src gets dst, and graph at dst gets src 
            graph[src].append(dst)
            graph[dst].append(src)

        # answer is set to -1 for length nL 
        answer = [-1] * nL
        # frontier is set as list of node id and neighbor graphical dictionary 
        frontier = [[0, {}]]
        # next frontier is set as needed 
        next_frontier = [] 
        # seen contains root to start 
        seen = set([0])
        # start at depth 0 
        depth = 0 
        # conduct BFS 
        while frontier : 
            # empty the frontier 
            for node, ancestors in frontier : 
                # at each step of doing so, set an index_depth paired tuple 
                # this stores the ancestor and the depth of the ancestor related
                index_depth = (-1, -1) 
                # for each ancestor in list cast of ancestors keys 
                for ancestor in list(ancestors.keys()) : 
                    # if ancestor in gcd set of nums at node 
                    if ancestor in self.gcd_set[nums[node]] : 
                        # get the ancestors index and depth from ancestors 
                        a_i, d_i = ancestors[ancestor]
                        # if the ancestors depth is greater than our current 
                        if d_i > index_depth[1] : 
                            # then they are a more recent thus closer to root, set in for this 
                            index_depth = (a_i, d_i)
                # answer at node is the ancestor's indexing that is closest to root 
                answer[node] = index_depth[0]
                # make a copy 
                copy = ancestors.copy()
                # set into the copy at the value of nums at node the values of this node and this depth 
                copy[nums[node]] = (node, depth)
                # this stores this for next loop of bfs progression 
                for neighbor in graph[node] : 
                    # if neighbor of graph at node is not yet visited 
                    if neighbor not in seen : 
                        # visit it on the next loop and prevent adding it twice 
                        seen.add(neighbor)
                        next_frontier.append([neighbor, copy])
            # at the end of emptying the current frontier, set up the next 
            frontier = next_frontier
            # increase depth and reset next frontier appropriately 
            depth += 1 
            next_frontier = [] 
            
        # return when done 
        return answer
1732