1using System;
2
3public class 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    private int Gcd(int a, int b) {
41        while (b != 0) {
42            int t = b;
43            b = a % b;
44            a = t;
45        }
46        return a;
47    }
48
49    public bool CanTraverseAllPairs(int[] nums) {
50        int n = nums.Length;
51        UnionFind uf = new UnionFind(n);
52
53        for (int i = 0; i < n; i++) {
54            for (int j = i + 1; j < n; j++) {
55                if (Gcd(nums[i], nums[j]) > 1) {
56                    uf.Union(i, j);
57                }
58            }
59        }
60        int root = uf.Find(0);
61        for (int i = 1; i < n; i++) {
62            if (uf.Find(i) != root) {
63                return false;
64            }
65        }
66        return true;
67    }
68
69    public static void Main() {
70        Solution sol = new Solution();
71        int[] nums = new int[] {2, 3, 6};
72        Console.WriteLine(sol.CanTraverseAllPairs(nums));
73    }
74}
75