33OJ
登录 注册

#P17765. 「LDOI R2」平方数 / Square

    ID: 20379 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 显示难度普及+/提高− 上传者: 标签>数学洛谷原创O2优化广度优先搜索 BFS图论建模最短路洛谷月赛

「LDOI R2」平方数 / Square

Problem Description

There are nn given pairs (ai,bi)(a_i, b_i).

A sequence p1,p2,…,pm (1≤pi≤n)p_1, p_2, \dots, p_m\ (1\le p_i\le n) of length m (m>1)m\ (m>1) is considered a good sequence if and only if it satisfies the following conditions:

  • pip_i are different from each other.

  • ap1a_{p_1} is a perfect square.

  • bpmb_{p_m} is a perfect square.

  • ∀1≤i<m\forall 1 \le i < m, api+1bpia_{p_{i+1}} b_{p_i} is a perfect square.

Find the minimum value of mm among all good sequences, or output −1-1 if there are no good sequences.

Input Format

There are multiple test cases for this problem.

The first line contains an integer TT, representing the number of test cases. Next, for each test case:

The first line contains an integer nn.

The next nn lines each contain two positive integers. The two numbers in line i+1i+1 represent ai,bia_i, b_i.

Output Format

For each test case:

If there are good sequences, output the minimum value of mm among all good sequences. If there are no good sequences, output −1-1.

3
5
4 5
20 9
8 9
16 3
12 2
1
1 1
2
1 1
1 1
2
-1
2
1
9
5 9
8 2
9 3
5 4
6 5
3 5
2 4
8 5
9 3
3

Hint

Explanation

Sample 11 Explanation: For the first test case, consider the sequence [1,2][1,2], a1=4a_1=4, b1a2=100b_1a_2=100, b2=9b_2=9 are all perfect squares, and the length of the sequence is 22. [4,5,3][4,5,3] is also a good sequence, but its length of 33 is not optimal.

Constraints

This problem uses subtask scoring.

Subtask ∑n≤\sum n \le Score
11 1010 2020
22 400400 4040
33 20002000

For all test cases, 1≤ai,bi≤1051\le a_i, b_i \le 10^5,3≤n,∑n≤20003 \le n, \sum n \le 2000.

Hint

nn is a perfect square if and only if there exists an integer xx that satisfies n=x2n=x^2.