New update is available. Click here to update.

Last Updated: 16 Apr, 2021

Difficulty: Hard

```
1) The value associated with the ‘ROOT’ node of the tree is considered zero.
2) Two integers ‘A’ and ‘B’ are coprime if the only positive integer that evenly divides (is a divisor of) both of them is 1, i.e., GCD(A, B) = 1 where GCD(A, B) is the greatest common divisor of ‘A’ and ‘B’.
3) Any node on the shortest path from ‘i’th node to the root is the ancestor of the ‘i’th node.
4) A node is not considered an ancestor of itself.
5) A graph is said to be a connected undirected graph if all the edges are bidirectional and there is a path between every pair of distinct vertices of the graph.
```

```
The first line of input contains an integer 'T' representing the number of test cases.
The first line of each test case contains an integer ‘N’ representing the number of nodes in the tree.
The second line of each test case contains ‘N’ space-separated integers representing the elements of the ‘NODES’ array.
The next ‘N - 1’ lines of each test case contain two space-separated integers, ‘U’ and ‘V’, representing an edge between ‘U’ and ‘V’.
```

```
For each test case, print a ‘N’ size array, ’RESULT’ where RESULT[i] = the closest ancestor to ‘i’th node such that NODES[ i ] and NODES[RESULT[ i ]] are coprime, else if no such ancestor found, RESULT[ i ] = -1.
The output of each test case will be printed in a separate line.
```

```
1 <= T <= 5
1 <= N <= 2000
|EDGES[ i ]| = 2
1 <= NODES[ i ] <= 20
EDGES[ i ] = {Ui, Vi} where 0 <= Ui, Vi < N
Ui != Vi
Where ‘|EDGES[ i ]| is the length of ‘i’ the array in ‘EDGES’, ‘NODES[ i ]’ is the ‘i’th element in the ‘NODES’ array, ‘EDGES[ i ]’ is the ‘i’th array of two integers ‘Ui’ and ‘Vi’ in the 2 - D array, ‘EDGES’.
Time limit: 1 sec
```

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

SIMILAR PROBLEMS

The Summit

Posted: 15 Sep, 2022

Difficulty: Easy

Rotting Oranges

Posted: 15 Sep, 2022

Difficulty: Moderate

Distance to a Cycle in Undirected Graph

Posted: 7 Nov, 2022

Difficulty: Moderate

Merge Two Sorted Arrays Without Extra Space

Posted: 19 Nov, 2022

Difficulty: Moderate

Co-Prime

Posted: 14 Dec, 2022

Difficulty: Hard

Popular Interview Problems: