<p>You are given an integer array <code>nums</code>. A subsequence of <code>nums</code> is called a <strong>square streak</strong> if:</p>

<ul>
	<li>The length of the subsequence is at least <code>2</code>, and</li>
	<li><strong>after</strong> sorting the subsequence, each element (except the first element) is the <strong>square</strong> of the previous number.</li>
</ul>

<p>Return<em> the length of the <strong>longest square streak</strong> in </em><code>nums</code><em>, or return </em><code>-1</code><em> if there is no <strong>square streak</strong>.</em></p>

<p>A <strong>subsequence</strong> is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.</p>

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

<pre>
<strong>Input:</strong> nums = [4,3,6,16,8,2]
<strong>Output:</strong> 3
<strong>Explanation:</strong> Choose the subsequence [4,16,2]. After sorting it, it becomes [2,4,16].
- 4 = 2 * 2.
- 16 = 4 * 4.
Therefore, [4,16,2] is a square streak.
It can be shown that every subsequence of length 4 is not a square streak.
</pre>

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

<pre>
<strong>Input:</strong> nums = [2,3,5,6,7]
<strong>Output:</strong> -1
<strong>Explanation:</strong> There is no square streak in nums so return -1.
</pre>

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

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

import math
class UnionFind:

    def __init__(self):
        self._parents = {}
        self._largest_size = 0

    def insert_node(self, number):
        if number not in self._parents:
            self._parents[number] = -1

    def get_parent(self, u):
        if u not in self._parents:
            return None
        if self._parents[u] < 0:
            return u
        node_parent = self.get_parent(self._parents[u])
        self._parents[u] = node_parent
        return node_parent

    def union(self, u, v):
        u_node_leader = self.get_parent(u)
        v_node_leader = self.get_parent(v)

        if not u_node_leader or not v_node_leader or u_node_leader == v_node_leader:
            return

        u_cluster_size = -1 * self._parents[u_node_leader]
        v_cluster_size = -1 * self._parents[v_node_leader]

        if v_cluster_size < u_cluster_size:
            u_node_leader, v_node_leader = v_node_leader, u_node_leader
        
        self._parents[v_node_leader] = u_node_leader
        self._parents[u_node_leader] = -1 * (u_cluster_size + v_cluster_size)

        self._largest_size = max(self._largest_size, self._parents[u_node_leader] * -1)        

    def get_largest_size(self):
        print(self._parents)
        return self._largest_size

class Solution:
    def longestSquareStreak(self, nums: List[int]) -> int:
        uf = UnionFind()
        for num in nums:
            uf.insert_node(num)
            uf.union(num, num * num)

            num_sqrt = int(math.sqrt(num))
            if num == num_sqrt * num_sqrt:
                uf.union(num, num_sqrt)

        square_streak = -1
        union_find_largest_size = uf.get_largest_size()
        if union_find_largest_size >= 2:
            square_streak = union_find_largest_size
        return square_streak

913