P17765 「LDOI R2」平方数 / Square

There are $n$ given pairs $(a_i, b_i)$. A sequence $p_1, p_2, \dots, p_m\ (1\le p_i\le n)$ of length $m\ (m>1)$ is considered a good sequence if and only if it satisfies the following conditions: + $p_i$ are different from each other. + $a_{p_1}$ is a perfect square. + $b_{p_m}$ is a perfect square. + $\forall 1 \le i < m$, $a_{p_{i+1}} b_{p_i}$ is a perfect square. Find the minimum value of $m$ among all good sequences, or output $-1$ if there are no good sequences.

**There are multiple test cases for this problem.** The first line contains an integer $T$, representing the number of test cases. Next, for each test case: The first line contains an integer $n$. The next $n$ lines each contain two positive integers. The two numbers in line $i+1$ represent $a_i, b_i$.

For each test case: If there are good sequences, output the minimum value of $m$ among all good sequences. If there are no good sequences, output $-1$.

### Explanation Sample $1$ Explanation: For the first test case, consider the sequence $[1,2]$, $a_1=4$, $b_1a_2=100$, $b_2=9$ are all perfect squares, and the length of the sequence is $2$. $[4,5,3]$ is also a good sequence, but its length of $3$ is not optimal. ### Constraints **This problem uses subtask scoring.** | Subtask | $\sum n \le$ | Score | |:-:|:-:|:-:| | $1$ | $10$ | $20$ | | $2$ | $400$ | $40$ | | $3$ | $2000$ | $40$ | For all test cases, $1\le a_i, b_i \le 10^5$，$3 \le n, \sum n \le 2000$. ### Hint $n$ is a perfect square if and only if there exists an integer $x$ that satisfies $n=x^2$.