<p>You are given a <strong>0-indexed</strong> integer array <code>nums</code>, and you are allowed to <strong>traverse</strong> between its indices. You can traverse between index <code>i</code> and index <code>j</code>, <code>i != j</code>, if and only if <code>gcd(nums[i], nums[j]) &gt; 1</code>, where <code>gcd</code> is the <strong>greatest common divisor</strong>.</p>

<p>Your task is to determine if for <strong>every pair</strong> of indices <code>i</code> and <code>j</code> in nums, where <code>i &lt; j</code>, there exists a <strong>sequence of traversals</strong> that can take us from <code>i</code> to <code>j</code>.</p>

<p>Return <code>true</code><em> if it is possible to traverse between all such pairs of indices,</em><em> or </em><code>false</code><em> otherwise.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,3,6]
<strong>Output:</strong> true
<strong>Explanation:</strong> In this example, there are 3 possible pairs of indices: (0, 1), (0, 2), and (1, 2).
To go from index 0 to index 1, we can use the sequence of traversals 0 -&gt; 2 -&gt; 1, where we move from index 0 to index 2 because gcd(nums[0], nums[2]) = gcd(2, 6) = 2 &gt; 1, and then move from index 2 to index 1 because gcd(nums[2], nums[1]) = gcd(6, 3) = 3 &gt; 1.
To go from index 0 to index 2, we can just go directly because gcd(nums[0], nums[2]) = gcd(2, 6) = 2 &gt; 1. Likewise, to go from index 1 to index 2, we can just go directly because gcd(nums[1], nums[2]) = gcd(3, 6) = 3 &gt; 1.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [3,9,5]
<strong>Output:</strong> false
<strong>Explanation:</strong> No sequence of traversals can take us from index 0 to index 2 in this example. So, we return false.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [4,3,12,8]
<strong>Output:</strong> true
<strong>Explanation:</strong> There are 6 possible pairs of indices to traverse between: (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), and (2, 3). A valid sequence of traversals exists for each pair, so we return true.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution {
public:
    vector<int> primes = {2, 3, 5, 7, 11, 13, 17, 19};

    void generate_primes() {
        for (int i = 21; i <= 5e4; i += 2) {
            bool flag = true;
            for (const int& j : primes) {
                if (j * j > i)
                    break;

                if (i % j == 0) {
                    flag = false;
                    break;
                }
            }

            if (flag)
                primes.emplace_back(i);
        }
    }

    long long toLongLong(const pair<int, int>& p) {
        return (long long)p.first + ((long long)p.second << 32);
    }

    pair<int, int> toPair(const long long& l) {
        const int a = (l & (int)INT_MAX);
        const int b = l >> 32;
        return {a, b};
    }

    unordered_set<long long> edges;

    bool canTraverseAllPairs(const vector<int>& nums) {
        const int one = *min_element(nums.begin(), nums.end());
        const int ninety = *max_element(nums.begin(), nums.end());
        if (one == 1) {
            if (nums.size() == 1)
                return true;
            else
                return false;
        }

        if (one == ninety)
            return true;

        generate_primes();
        unordered_set<int> to_visit;

        for (const int n : nums) {
            vector<int> factors;
            for (const int& j : primes) {
                if (j > n)
                    break;

                if (n % j == 0)
                    factors.push_back(j);
            }

            if (factors.size() == 0) {
                return false;
            } else if (factors.size() == 1) {
                to_visit.insert(min(factors.front(), n));
                continue;
            }

            for (int i = 0; i < (int)factors.size() - 1; i++)
                for (int j = i + 1; j < (int)factors.size(); j++)
                    edges.insert(toLongLong({factors[i], factors[j]}));
        }

        unordered_map<int, vector<int>> umv;
        for (const long long l : edges) {
            const pair<int, int> p = toPair(l);
            // cout << p.first << "." << p.second << " ";
            umv[p.first].push_back(p.second);
            umv[p.second].push_back(p.first);
            to_visit.insert(p.first);
            to_visit.insert(p.second);
        }

        // cout << '\n';
        // for (const int i : to_visit)
        //     cout << i << " ";

        int seed;
        for (const int i : to_visit) {
            seed = i;
            to_visit.erase(i);
            break;
        }
        queue<int> q;
        q.push(seed);

        while (!q.empty()) {
            const int t = q.front();
            q.pop();

            for (const int& i : umv[t])
                if (to_visit.count(i)) {
                    to_visit.erase(i);
                    q.push(i);
                }
        }

        return to_visit.empty();
        // return 0;
    }
};
156312