<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>

class DSU:

    def __init__(self, nums):
        self.repr = {}
        self.sizes = {}
        for num in nums:
            self.repr[num] = num
            self.sizes[num] = 1
        self.max_size = 1
    
    def contains(self, v):
        return v in self.repr

    def find(self, v):
        root = v
        while root != self.repr[root]:
            root = self.repr[root]
        return root

    def union(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)
        if root_u == root_v:
            return
        if self.sizes[root_u] > self.sizes[root_v]:
            self.repr[root_v] = root_u
            self.sizes[root_u] += self.sizes[root_v]
            self.max_size = max(self.max_size, self.sizes[root_u])
        else:
            self.repr[root_u] = root_v
            self.sizes[root_v] += self.sizes[root_u]
            self.max_size = max(self.max_size, self.sizes[root_v])


class Solution:
    def longestSquareStreak(self, nums: List[int]) -> int:
        dsu = DSU(nums)

        for num in nums:
            square = num * num
            if dsu.contains(square):
                dsu.union(num, num*num)
        
        max_size = dsu.max_size

        return -1 if max_size == 1 else max_size
        
42400