func_code_string: #include <bits/stdc++.h>   using namespace std;   vector<int> prime;   int isprime[1000005];   void Find() {     for (int i = 2; i < 1000005; i++) {       if (isprime[i] == 0) {         prime.push_back(i);         for (int j = i * 2; j < 1000005; j += i) isprime[j] = 1;       }     }   }   vector<int> v[1000005];   int dis[1000005];   int from[1000005];   int main() {     int n;     scanf( %d , &n);     vector<int> vv;     for (int i = 2; i <= 1000; i++) {       vv.push_back(i * i);     }     vector<int> ok, ok2;     Find();     for (int i = 1; i <= n; i++) {       int first;       scanf( %d , &first);       for (auto it : vv) {         while (first % it == 0) first /= it;       }       if (first == 1) {         printf( 1 n );         return 0;       }       if (isprime[first] == 0)         ok.push_back(first);       else {         for (int j = 2; j < 1000; j++) {           if (first % j == 0) {             v[first / j].push_back(j);             v[j].push_back(first / j);             break;           }         }         ok2.push_back(first);       }     }     sort(ok.begin(), ok.end());     for (int i = 1; i < ok.size(); i++) {       if (ok[i] == ok[i - 1]) {         printf( 2 n );         return 0;       }     }     sort(ok2.begin(), ok2.end());     for (int i = 1; i < ok.size(); i++) {       if (ok[i] == ok[i - 1]) {         printf( 2 n );         return 0;       }     }     queue<int> q;     memset(dis, -1, sizeof(dis));     for (auto it : ok) {       dis[it] = 0;       q.push(it);     }     int ans = 1e9;     while (!q.empty()) {       int first = q.front();       q.pop();       for (auto it : v[first]) {         if (dis[it] == -1) {           dis[it] = dis[first] + 1;           from[it] = first;           q.push(it);         } else {           if (from[first] == it)             ;           else {             ans = min(ans, dis[it] + dis[first] + 1 + 2);           }         }       }     }     for (auto it : prime) {       if (it > 1000) break;       for (auto it2 : prime) dis[it2] = -1;       dis[it] = 0;       queue<int> q;       q.push(it);       while (!q.empty()) {         int first = q.front();         q.pop();         for (auto it2 : v[first]) {           if (dis[it2] == -1) {             dis[it2] = dis[first] + 1;             from[it2] = first;             q.push(it2);           } else {             if (from[first] == it2)               ;             else {               ans = min(ans, dis[first] + dis[it2] + 1);             }           }         }       }     }     if (ans == 1e9) {       printf( -1 n );     } else {       printf( %d n , ans);     }   }   