# Description

You are given an array a of length n that has a special condition: every element in this array has at most 7 divisors. Find the length of the shortest non-empty subsequence of this array product of whose elements is a perfect square.

A sequence a is a subsequence of an array b if a can be obtained from b by deletion of several (possibly, zero or all) elements.

Input
The first line contains an integer n ($1 \le n \le 10^5$) — the length of a.

The second line contains n integers $a_1,a_2,\dots,a_n$ ($1 \le a_i \le 10^6$) — the elements of the array a.

Output
Output the length of the shortest non-empty subsequence of a product of whose elements is a perfect square. If there are several shortest subsequences, you can find any of them. If there's no such subsequence, print "-1".

Examples
input
3
1 4 6
output
1
input
4
2 3 6 6
output
2
input
3
6 15 10
output
3
input
4
2 3 5 7
output
-1
Note
In the first sample, you can choose a subsequence $[1]$.

In the second sample, you can choose a subsequence $[6,6]$.

In the third sample, you can choose a subsequence $[6,15,10]$.

In the fourth sample, there is no such subsequence.

# Problem solving

every element in this array has at most 7 divisors，题目中的这句话很关键，说的是序列中的数最多有7个因子。

$p,q$均为质数。如果出现了为$1$的情况，那直接输出$1$即可。因为你可以只选择这一个数。

$bfs$来找最小环，只要下一个点是被之前访问过的，更新$ans$的最小值即可,$ans=\min\{ans,dep_{to}+dep_x+1\}$$dep_{to}$$dep_x$代表的是从当前的起点到$to$$x$的距离，最后加的$1$就是将$to$$x$中间的那个距离。

# Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+10;
const int inf =  0x3f3f3f3f;
vector<ll> V[maxn];
int dis[maxn],f[maxn];
int ans=inf;
#define pb push_back
void bfs(int u) {
memset(dis, inf, sizeof(dis));
dis[u] = 0;
queue<int> q;
q.push(u);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = 0; i < V[u].size(); i++) {
int v = V[u][i];
if (v != f[u]) {
if (dis[v] != inf) ans = min(ans, (dis[u] + dis[v] + 1));
else f[v] = u, dis[v] = dis[u] + 1, q.push(v);;
}
}
}
}
int main()
{
ios::sync_with_stdio(0);
int n,x;
cin>>n;
for(int i=0;i<n;i++){
cin>>x;
int flag=0;
for(int i=2;i<=sqrt(x);i++){
while(x%(i*i)==0)    x/=i*i;
}
if(x==1){
cout<<"1\n";
return 0;
}
for(int i=2;i<=sqrt(x);i++){
if(x%i==0){
V[i].pb(x/i);
V[x/i].pb(i);
flag=1;
}
}
if(!flag){
V[1].pb(x);
V[x].pb(1);
}
}
for(int i=1;i<=sqrt(maxn);i++)    bfs(i);
if(ans!=inf)    cout<<ans<<endl;
else cout<<"-1"<<endl;
return 0;
}