<p>You are given an integer array <code>nums</code>, and you can perform the following operation <strong>any</strong> number of times on <code>nums</code>:</p>

<ul>
	<li>Swap the positions of two elements <code>nums[i]</code> and <code>nums[j]</code> if <code>gcd(nums[i], nums[j]) &gt; 1</code> where <code>gcd(nums[i], nums[j])</code> is the <strong>greatest common divisor</strong> of <code>nums[i]</code> and <code>nums[j]</code>.</li>
</ul>

<p>Return <code>true</code> <em>if it is possible to sort </em><code>nums</code><em> in <strong>non-decreasing</strong> order using the above swap method, 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 = [7,21,3]
<strong>Output:</strong> true
<strong>Explanation:</strong> We can sort [7,21,3] by performing the following operations:
- Swap 7 and 21 because gcd(7,21) = 7. nums = [<u><strong>21</strong></u>,<u><strong>7</strong></u>,3]
- Swap 21 and 3 because gcd(21,3) = 3. nums = [<u><strong>3</strong></u>,7,<u><strong>21</strong></u>]
</pre>

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

<pre>
<strong>Input:</strong> nums = [5,2,6,2]
<strong>Output:</strong> false
<strong>Explanation:</strong> It is impossible to sort the array because 5 cannot be swapped with any other element.
</pre>

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

<pre>
<strong>Input:</strong> nums = [10,5,9,3,15]
<strong>Output:</strong> true
We can sort [10,5,9,3,15] by performing the following operations:
- Swap 10 and 15 because gcd(10,15) = 5. nums = [<u><strong>15</strong></u>,5,9,3,<u><strong>10</strong></u>]
- Swap 15 and 3 because gcd(15,3) = 3. nums = [<u><strong>3</strong></u>,5,9,<u><strong>15</strong></u>,10]
- Swap 10 and 15 because gcd(10,15) = 5. nums = [3,5,9,<u><strong>10</strong></u>,<u><strong>15</strong></u>]
</pre>

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

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

class Solution:
    def gcdSort(self, nums: List[int]) -> bool:
        n = len(nums)
        cur_group = -1
        groups = []
        num_labels = [-1] * n
        for i in range(0, n):
            for j in range(0, len(groups)):
                if math.gcd(groups[j], nums[i]) != 1:
                    groups[j] = math.lcm(groups[j], nums[i])
                    num_labels[i] = j
                    break
            if num_labels[i] == -1:
                cur_group += 1
                groups.append(nums[i])
                num_labels[i] = cur_group
        group_edges = [list() for i in range(0, len(groups))]
        for i in range(0, cur_group):
            for j in range(0, cur_group+1):
                if math.gcd(groups[i], groups[j]) != 1:
                    group_edges[i].append(j)
                    group_edges[j].append(i)
        used_group = [False for group in groups]
        combined_groups = []
        for i in range(0, cur_group + 1):
            if used_group[i]:
                continue
            cur_comb_group = set()
            path = deque()
            path.append(i)
            used_group[i] = True
            cur_comb_group.add(i)
            while len(path) > 0:
                cur_group_i = path.popleft()
                for next_group_i in group_edges[cur_group_i]:
                    if used_group[next_group_i]:
                        continue
                    used_group[next_group_i] = True
                    cur_comb_group.add(next_group_i)
                    path.append(next_group_i)
            combined_groups.append(cur_comb_group)
        intended_section = [None] * len(groups)
        for i, comb_group in enumerate(combined_groups):
            for group_i in comb_group:
                intended_section[group_i] = i
        sections = [list() for i in range(0, len(combined_groups))]
        for i in range(0, n):
            sections[intended_section[num_labels[i]]].append(i)
        #print(sections)
        result_array = [None] * n
        for section in sections:
            sub_nums = sorted([nums[i] for i in section])
            for j, i in enumerate(section):
                result_array[i] = sub_nums[j]
        for i in range(0, n-1):
            if result_array[i] > result_array[i+1]:
                return False
        return True

    def gcdSort_bad3(self, nums: List[int]) -> bool:
        n = len(nums)
        cur_group = -1
        edge_labels = [-1] * n
        #unassigned = deque(range(0, n))
        lol_is = list(range(0, n))
        lol_is = sorted(lol_is, key=lambda x : nums[x])
        unassigned = deque(lol_is)
        for i in lol_is:
            #print("procing {}: {}".format(i, edge_labels))
            if edge_labels[i] != -1:
                continue
            cur_group += 1
            nums_to_start_from = deque()
            nums_to_start_from.append(i)
            while len(nums_to_start_from) > 0:
                cur_start = nums_to_start_from.popleft()
                next_unassigned = deque()
                for j in unassigned:
                    if edge_labels[j] != -1:
                        continue
                    if math.gcd(nums[cur_start], nums[j]) == 1:
                        next_unassigned.append(j)
                        continue
                    edge_labels[j] = cur_group
                    nums_to_start_from.append(j)
                unassigned = next_unassigned
        #print(edge_labels)
        sections = [list() for i in range(0, cur_group+1)]
        for i in range(0, n):
            sections[edge_labels[i]].append(i)
        del edge_labels
        #for row in sections:
        #    print(row)
        result_array = [None] * n
        for section in sections:
            sub_nums = sorted([nums[i] for i in section])
            for j, i in enumerate(section):
                result_array[i] = sub_nums[j]
        for i in range(0, n-1):
            if result_array[i] > result_array[i+1]:
                return False
        return True

    def gcdSort_bad2(self, nums: List[int]) -> bool:
        n = len(nums)
        cur_group = -1
        edge_labels = [-1] * n
        for i in range(0, n):
            #print("procing {}: {}".format(i, edge_labels))
            if edge_labels[i] != -1:
                continue
            cur_group += 1
            nums_to_start_from = deque()
            nums_to_start_from.append(i)
            while len(nums_to_start_from) > 0:
                cur_start = nums_to_start_from.popleft()
                for j in range(0, n):
                    if edge_labels[j] != -1:
                        continue
                    if math.gcd(nums[cur_start], nums[j]) == 1:
                        continue
                    edge_labels[j] = cur_group
                    nums_to_start_from.append(j)
        print(edge_labels)
        sections = [list() for i in range(0, cur_group+1)]
        for i in range(0, n):
            sections[edge_labels[i]].append(i)
        del edge_labels
        #for row in sections:
        #    print(row)
        result_array = [None] * n
        for section in sections:
            sub_nums = sorted([nums[i] for i in section])
            for j, i in enumerate(section):
                result_array[i] = sub_nums[j]
        for i in range(0, n-1):
            if result_array[i] > result_array[i+1]:
                return False
        print(result_array)
        
        return True


    def gcdSort_bad(self, nums: List[int]) -> bool:
        n = len(nums)
        edges = [list() for i in range(0, n)]
        for i in range(0, n-1):
            for j in range(i+1, n):
                if math.gcd(nums[i], nums[j]) == 1:
                    continue
                edges[i].append(j)
                edges[j].append(i)
        edge_labels = [-1] * n
        cur_group = -1
        for i in range(0, n):
            if edge_labels[i] != -1:
                continue
            cur_group += 1
            path = deque()
            path.append(i)
            edge_labels[i] = cur_group
            while len(path) > 0:
                cur_i = path.pop()
                for next_i in edges[cur_i]:
                    if edge_labels[next_i] != -1:
                        continue
                    edge_labels[next_i] = cur_group
                    path.append(next_i)
        del edges
        sections = [list() for i in range(0, cur_group+1)]
        for i in range(0, n):
            sections[edge_labels[i]].append(i)
        del edge_labels
        #for row in sections:
        #    print(row)
        result_array = [None] * n
        for section in sections:
            sub_nums = sorted([nums[i] for i in section])
            for j, i in enumerate(section):
                result_array[i] = sub_nums[j]
        for i in range(0, n-1):
            if result_array[i] > result_array[i+1]:
                return False
        return True
22900