// Tree of Coprimes class Solution { vector co[51]; vector> st[51]; vector nums, ans; vector> e; void dfs(int u, int dep, int p) { int x = nums[u], maxd = -1; for (int y : co[x]) { auto &c = st[y]; if (c.size() && c.back().first > maxd) tie(maxd, ans[u]) = c.back(); } st[x].emplace_back(dep, u); for (int v : e[u]) if (v != p) dfs(v, dep+1, u); st[x].pop_back(); } public: vector getCoprimes(vector& nums, vector>& edges) { this->nums = nums; ans.assign(nums.size(), -1); e.resize(nums.size()); set n(nums.begin(), nums.end()); for (int a : n) for (int b : n) if (__gcd(a, b) == 1) co[a].push_back(b); for (auto &i : edges) { e[i[0]].push_back(i[1]); e[i[1]].push_back(i[0]); } dfs(0, 0, -1); return ans; } };