1import java.util.*;
2
3class UnionFind {
4    private int[] root;
5    private int[] rank;
6
7    public UnionFind(int size) {
8        root = new int[size];
9        rank = new int[size];
10        for (int i = 0; i < size; i++) {
11            root[i] = i;
12            rank[i] = 1;
13        }
14    }
15
16    public int find(int x) {
17        if (x == root[x]) {
18            return x;
19        }
20        return root[x] = find(root[x]);
21    }
22
23    public void union(int x, int y) {
24        int rootX = find(x);
25        int rootY = find(y);
26        if (rootX != rootY) {
27            if (rank[rootX] > rank[rootY]) {
28                root[rootY] = rootX;
29            } else if (rank[rootX] < rank[rootY]) {
30                root[rootX] = rootY;
31            } else {
32                root[rootY] = rootX;
33                rank[rootX]++;
34            }
35        }
36    }
37}
38
39public class Solution {
40    public boolean canTraverseAllPairs(int[] nums) {
41        int n = nums.length;
42        UnionFind uf = new UnionFind(n);
43
44        for (int i = 0; i < n; i++) {
45            for (int j = i + 1; j < n; j++) {
46                if (gcd(nums[i], nums[j]) > 1) {
47                    uf.union(i, j);
48                }
49            }
50        }
51        int root = uf.find(0);
52        for (int i = 1; i < n; i++) {
53            if (uf.find(i) != root) {
54                return false;
55            }
56        }
57        return true;
58    }
59
60    private int gcd(int a, int b) {
61        while (b != 0) {
62            int temp = b;
63            b = a % b;
64            a = temp;
65        }
66        return a;
67    }
68
69    public static void main(String[] args) {
70        Solution sol = new Solution();
71        int[] nums = {2, 3, 6};
72        System.out.println(sol.canTraverseAllPairs(nums));
73    }
74}
75