We have n cities labeled from 1 to n. Two different cities with labels x and y are directly connected by a bidirectional road if and only if x and y share a common divisor strictly greater than some threshold. More formally, cities with labels x and y have a road between them if there exists an integer z such that all of the following are true:


	x % z == 0,
	y % z == 0, and
	z &gt; threshold.


Given the two integers, n and threshold, and an array of queries, you must determine for each queries[i] = [ai, bi] if cities ai and bi are connected directly or indirectly.&nbsp;(i.e. there is some path between them).

Return an array answer, where answer.length == queries.length and answer[i] is true if for the ith query, there is a path between ai and bi, or answer[i] is false if there is no path.

&nbsp;
Example 1:

Input: n = 6, threshold = 2, queries = [[1,4],[2,5],[3,6]]
Output: [false,false,true]
Explanation: The divisors for each number:
1:   1
2:   1, 2
3:   1, 3
4:   1, 2, 4
5:   1, 5
6:   1, 2, 3, 6
Using the underlined divisors above the threshold, only cities 3 and 6 share a common divisor, so they are the
only ones directly connected. The result of each query:
[1,4]   1 is not connected to 4
[2,5]   2 is not connected to 5
[3,6]   3 is connected to 6 through path 3--6


Example 2:

Input: n = 6, threshold = 0, queries = [[4,5],[3,4],[3,2],[2,6],[1,3]]
Output: [true,true,true,true,true]
Explanation: The divisors for each number are the same as the previous example. However, since the threshold is 0,
all divisors can be used. Since all numbers share 1 as a divisor, all cities are connected.


Example 3:

Input: n = 5, threshold = 1, queries = [[4,5],[4,5],[3,2],[2,3],[3,4]]
Output: [false,false,false,false,false]
Explanation: Only cities 2 and 4 share a common divisor 2 which is strictly greater than the threshold 1, so they are the only ones directly connected.
Please notice that there can be multiple queries for the same pair of nodes [x, y], and that the query [x, y] is equivalent to the query [y, x].


&nbsp;
Constraints:


	2 &lt;= n &lt;= 104
	0 &lt;= threshold &lt;= n
	1 &lt;= queries.length &lt;= 105
	queries[i].length == 2
	1 &lt;= ai, bi &lt;= cities
	ai != bi


class Solution:
    def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]:
        parent = list(range(n+1))
        def find(i):
            if parent[i] != i:
                parent[i] = find(parent[i])
            return parent[i]
        def union(i,j):
            parent[find(i)] = find(j)
        if not threshold: return [True]*len(queries)
        for i in range(1, n+1):
            for j in range(2*i, n+1, i):
                if i > threshold: union(i,j)
        return [find(i) == find(j) for i,j in queries]
//Solving the problem using Disjoint Set Union Find approach

class Solution {

    public int find(int x){

        if(parent[x] == x)
            return x;

        //Optimising by placing the same parent for all the elements to reduce reduntant calls
        return parent[x] = find(parent[x]);
    }

    public void union(int a, int b){

        a = find(a);
        b = find(b);

        //Using Rank optimisation
        if(rank[a] > rank[b]){
            parent[b] = a;
            rank[a] += rank[b];
        }

        else{
            parent[a] = b;
            rank[b] += rank[a];
        }

        //parent[b] = a;
    }

    int parent[];
    int rank[];
    public List<Boolean> areConnected(int n, int threshold, int[][] queries) {

        List<Boolean> ans = new ArrayList<Boolean>();
        parent = new int[n+1];
        rank = new int[n+1];

        for(int i=1; i<=n; i++){
            //Each element is its own parent
            parent[i] = i;
            //At beginning each element has rank 1
            rank[i] = 1;
        }

        // Finding the possible divisors with pairs above given threshold
        for(int th = threshold+1; th<=n; th++){

            int mul = 1;
            while(mul * th <= n){
                //If possible pair then making a union of those paired element
                union(th, mul*th);
                mul++;
            }
        }

        //Generating ans for all possible queries
        for(int[] query : queries){
            ans.add((find(query[0]) == find(query[1])));
        }
        return ans;
    }
}
// DSU Class Template
class DSU {
    vector<int> parent, size;
public:

    DSU(int n) {
        for(int i=0; i<=n; i++) {
            parent.push_back(i);
            size.push_back(1);
        }
    }

    int findParent(int num) {
        if(parent[num] == num) return num;
        return parent[num] = findParent(parent[num]);
    }

    void unionBySize(int u, int v) {
        int parU = findParent(u);
        int parV = findParent(v);

        if(parU == parV) return;

        if(size[parU] < size[parV]) {
            parent[parU] = parV;
            size[parV] += size[parU];
        }
        else {
            parent[parV] = parU;
            size[parU] += size[parV];
        }
    }
};

class Solution {
public:
    vector<bool> areConnected(int n, int threshold, vector<vector<int>>& queries) {

        DSU dsu(n);

        // Make connections with its multiple
        for(int i=threshold+1; i<=n; i++) {
            int j = 1;
            while(i*j <= n) {
                dsu.unionBySize(i, i*j);
                j++;
            }
        }

        vector<bool> res;
        for(auto& query : queries) {
            int u = query[0];
            int v = query[1];

            // Check if both cities belong to same component or not
            if(dsu.findParent(u) == dsu.findParent(v)) res.push_back(true);
            else res.push_back(false);
        }

        return res;
    }
};
var areConnected = function(n, threshold, queries) {

    // if(gcd(a,b)>threshold), a and b are connected

    // 2 is connected with : 2, 4,6,8,10,12,14,16, (gcd(2,y)=2)
    // 3 is connected with : 3,6,9,12,... (gcd(3,y)=3)
    // 4 is connected with : 4,8,12,16,20,24,28, (gcd(4,y)=4)
    // 6 is connected with : 6,12,18...,cos (gcd(6,y)=6)
    // 5 is connected with : 10,15,20,25,...n cos (gcd(5,y)=6)
    // etc

    let dsu=new UnionFind(n+1) //to map n=>n (no node 0 on my question)

    for (let node = threshold+1; node <=n; node++) //basically this ensures that the road exists
        //cos gcd(node,secondnode)==node >threshold
        for (let secondnode = node+node; secondnode <=n; secondnode+=node)
            dsu.union(node,secondnode)

    return queries.map(([a,b])=>dsu.sameGroup(a,b))
};
class UnionFind {

    constructor(size){
        //the total count of different elements(not groups) in this union find
        this.count=size
        //tracks the sizes of each of the components(groups/sets)
        //groupsize[a] returns how many elements the component with root a has
        this.groupSize=[...Array(size)]
        //number of components(groups) in the union find
        this.numComponents=size
        //points to the parent of i, if parent[i]=i, i is a root node
        this.parent=[...Array(size)] //which is also the index of the group

        //put every element into its own group
        // rooted at itself
        for (let i = 0; i < size; i++) {
            this.groupSize[i]=i
            this.parent[i]=i
        }
    }

    //returns to which component (group) my element belongs to
    // (n) --Amortized constant time
    // Update: Also compresses the paths so that each child points to its
    // parent
    find(element){
        let root=element
        //find the parent of the group the elemnt belongs to
        // When root===parent[root] is always the parent of that group (root)
        while(root!=this.parent[root])
            root=this.parent[root]

        // Compression, point the element to its parent if its not already pointed
        // Tldr: Not only do I point my element to its actual root, i point any
        // inbetween elements to that root aswell
        while(element!=root){
            let next=this.parent[element]
            this.parent[element]=root
            element=next
        }

        return root
    }

    //Unifies the sets containing A and B
    // if not already unified
    // (n) --Amortized constant time
    union(A,B){
        let root1=this.find(A) //parent of A
            ,root2=this.find(B) //parent of B
        if(root1===root2) //already unified
            return
        // I want to put the set with fewer elements
        // to the one with more elemenets
        if(this.groupSize[root1]<this.groupSize[root2]){
            this.groupSize[root2]+=this.groupSize[root1]
            this.parent[root1]=this.parent[root2]
        }
        else {
            this.groupSize[root1]+=this.groupSize[root2]
            this.parent[root2]=this.parent[root1]
        }

        this.numComponents-- //cos 1 less group, since i merged 2
    }

    //same parent=>samegroup
    sameGroup=(A,B)=>this.find(A)==this.find(B)

    //essentially the groupSize of its parent's group
    sizeOfGroup=(A)=>this.groupSize[this.find(A)]

}
Graph Connectivity With Threshold