func_code_string: #include <bits/stdc++.h>   using namespace std;   const int N = 1e5 + 1;   const int MAX = 1e6 + 1;   int n, f[MAX], dep[MAX];   int u[MAX], pr[MAX];   int stk[2][N], q[N << 1];   bool mk[MAX], cmp[N];   vector<int> a, adj[MAX], dv[MAX];   int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);     cout.tie(0);     cin >> n;     for (int i = 0; i < n; i++) {       a.push_back(0);       cin >> a[i];     }     fill(f, f + MAX, 0);     fill(u, u + MAX, -1);     fill(cmp, cmp + N, 1);     for (int i = 0; i < n; i++) {       int p1 = -1, p2 = -1;       int x = a[i], y, z = 1;       if (x == 1) {         f[1]++;         dv[1].push_back(1);         continue;       }       for (int j = 2; j < a[i]; j++) {         if (j * j > a[i]) break;         if (x % j == 0) {           y = 0;           if (p1 == -1)             p1 = j;           else             p2 = j;           while (x % j == 0) {             x /= j;             y ^= 1;           }           if (y)             z *= j;           else {             if (p2 == j)               p2 = -1;             else               p1 = -1;           }         }       }       if (x != 1) {         if (p1 == -1)           p1 = x;         else           p2 = x;         z *= x;       }       a[i] = z;       u[z] = i;       stk[0][i] = max(p1, 0);       stk[1][i] = max(p2, 0);       for (int j = 0; j < 2; j++) cmp[i] &= (stk[j][i] != 0);       if (cmp[i])         for (int j = 0; j < 2; j++) dv[stk[j][i]].push_back(stk[j ^ 1][i]);       else {         dv[1].push_back(z);         dv[z].push_back(1);       }       f[z]++;     }     if (f[1]) {       cout << 1 <<   n ;       return 0;     }     int mx = -1;     for (int x = 0; x < MAX; x++) mx = max(mx, f[x]);     if (mx > 1) {       cout << 2 <<   n ;       return 0;     }     fill(mk, mk + MAX, 0);     for (int x = 0; x < MAX; x++) {       for (auto& y : dv[x])         if (!mk[y]) {           mk[y] = 1;           adj[x].push_back(y);         }       for (auto& y : dv[x]) mk[y] = 0;     }     fill(pr, pr + MAX, 0);     for (int x = 0; x < MAX; x++)       for (auto& y : adj[x]) pr[y]++;     int l, r, mn = MAX;     mx = -1;     for (int x = 0; x < MAX; x++)       if (pr[x]) mx = max(mx, x);     mx = sqrt(mx) + 1;     fill(q, q + (N << 1), 0);     for (int x = 0; x < MAX; x++)       if (pr[x]) {         if (x > mx) continue;         fill(mk, mk + MAX, 0);         fill(dep, dep + MAX, 0);         l = 0;         r = 0;         dep[x] = 0;         mk[x] = 1;         q[r++] = x;         q[r++] = x;         while (l != r) {           int y = q[l++];           int z = q[l++];           for (auto& w : adj[y]) {             if (w == z) continue;             if (mk[w]) {               mn = min(mn, dep[w] + 1 + dep[y]);               continue;             }             dep[w] = 1 + dep[y];             mk[w] = 1;             q[r++] = w;             q[r++] = y;           }         }       }     if (mn == MAX) mn = -1;     cout << mn <<   n ;     return 0;   }   