You are given $n$ integer numbers $a_1, a_2, \dots, a_n$. Consider graph on $n$ nodes, in which nodes $i$, $j$ ($i\neq j$) are connected if and only if, $a_i$ AND $a_j\neq 0$, where AND denotes the bitwise AND operation.

Find the length of the shortest cycle in this graph or determine that it doesn't have cycles at all.


-----Input-----

The first line contains one integer $n$ $(1 \le n \le 10^5)$ — number of numbers.

The second line contains $n$ integer numbers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^{18}$).


-----Output-----

If the graph doesn't have any cycles, output $-1$. Else output the length of the shortest cycle.


-----Examples-----
Input
4
3 6 28 9

Output
4
Input
5
5 12 9 16 48

Output
3
Input
4
1 2 4 8

Output
-1


-----Note-----

In the first example, the shortest cycle is $(9, 3, 6, 28)$.

In the second example, the shortest cycle is $(5, 12, 9)$.

The graph has no cycles in the third example.

Difficulty: competition

Starter code:

Solutions:
from collections import deque
bits = [0] * 64
n = int(input())
data = list([x for x in map(int, input().split()) if x != 0])
n = len(data)
if n == 0:
    print(-1)
    return
for v in data:
    i = 0
    while v != 0:
        bits[i] += v & 1
        i += 1
        v >>= 1
for i in range(64):
    if bits[i] > 2:
        print(3)
        return
graph = [[] for _ in range(n)]
for u in range(n):
    for v in range(u):
        if (data[u] & data[v]) != 0 and u != v:
            graph[v].append(u)
            graph[u].append(v)


def bfs(start):
    group = [-1] * n
    depth = [0] + [-1] * (n - 1)
    for j in range(len(graph[start])):
        to = graph[start][j]
        group[to] = j
        depth[to] = 1
    bfsQ = deque(graph[start])
    minlen = 999999999
    while len(bfsQ) > 0:
        u = bfsQ[0]
        bfsQ.popleft()
        for v in graph[u]:
            if v == start:
                if depth[u] < 2:
                    continue
                return depth[u] + 1
            if group[v] == -1:
                group[v] = group[u]
                depth[v] = depth[u] + 1
                bfsQ.append(v)
            elif group[v] != group[u]:
                newlen = depth[u] + depth[v] + 1
                if newlen < minlen:
                    minlen = newlen
    return minlen


answer = min(list(map(bfs, list(range(n)))))
print(answer if answer <= n else -1)


from collections import Counter, deque

n = int(input())
arr = list([x for x in map(int, input().strip().split()) if x != 0])

'''
for i, a in enumerate(arr):
    for j, b in enumerate(arr):
        if a & b != 0 and i != j:
            print(i,j,a,b)
return
'''

c = Counter()

for each in arr:
    for b in range(0, 64):
        if (1 << b) & each != 0:
            c[b] += 1
            if c[b] >= 3:
                print(3)
                return

ans = 1234567

for idx, st in enumerate(arr):
    dists = {}
    q = deque()
    q.append((idx, -1))
    dists[idx] = 0

    while q:
        node, par = q[0]
        dist = dists[node]
        q.popleft()
        for idx2, v in enumerate(arr):
            if idx2 == par:
                continue
            if idx2 == node or (v & arr[node]) == 0:
                continue
            if idx2 in dists:
                candidate = dists[idx2] + dist + 1
                if candidate != 2:
                    ans = min(ans, candidate)
                continue
            dists[idx2] = dist + 1
            q.append((idx2, node))


if ans == 1234567:
    print(-1)
else:
    print(ans)


import sys
n=int(input())
a=[]

for x in input().split():
    if(int(x)!=int(0)):
        a.append(int(x))

if(len(a)>500):
    print(3)
    return

n=len(a)

#print(n)

g=[]
for i in range(n):
   g.append([])

for i in range(n):
    for j in range(n):
        g[i].append(1000000000)

for i in range(n):
    for j in range(n):
        if(i!=j and (a[i]&a[j])!=0):
            g[i][j]=1


ans=int(10000000000)

dis=[]
for i in range(n):
    dis.append([])

for i in range(n):
    for j in range(n):
        dis[i].append(g[i][j])

for  k in range(n):
    for i in range(k):
        for j in range(i+1,k):
            ans=min(ans,dis[i][j]+g[i][k]+g[k][j])
    for i in range(n):
        for j in range(n):
            dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j])



if(ans>1000):
    print(-1)
else:
    print(ans)


import sys
from collections import deque

n = int(input())
a = list(map(int, input().split()))
na = list()
for x in a:
    if (x):
        na.append(x)
a = na
n = len(a)
for b in range(60):
    cnt = 0
    for x in a:
        if (x >> b & 1):
            cnt += 1
    if (cnt >= 3) :
        print(3)
        return
g = [list() for x in range(n)]
for i in range(n):
    for j in range (n):
        if (i != j and (a[i] & a[j])):
            g[i].append(j)
ans = 200
def go(r):
    nonlocal ans
    d = [-1 for x in range(n)]
    q = deque()
    d[r] = 0
    q.append(r)
    while (len(q)):
        v = q.popleft()
        for u in g[v]:
            if (d[u] == -1):
                d[u] = d[v] + 1
                q.append(u)
            elif (d[u] >= d[v]):
                ans = min(ans, d[v] + d[u] + 1)
for r in range(n):
    go(r)
if (ans > n) :
    ans = -1
print(ans)

from collections import defaultdict

n = int(input())

arr = list(map(int, input().split()))

d = defaultdict(list)
dd = defaultdict(list)

for i, el in enumerate(arr):
    b = '{0:b}'.format(el)[::-1]
    for j, digit in enumerate(b):
        if digit == '1':
            for i2 in d[j]:
                dd[i].append(i2)
                dd[i2].append(i)
            d[j].append(i)
        if len(d[j]) == 3:
            print(3)
            return

colors = {i: [] for i in range(len(arr))}

min_cycle = float('+inf')

for i in range(len(arr)):
    if colors[i]:
        continue
    tier = [(i, [])]
    next_tier = []
    while tier:
        for t, way in tier:
            if colors[t]:
                c = 0
                while len(way) > c and len(colors[t]) > c and way[c] == \
                        colors[t][c]:
                    c += 1
                min_cycle = min(len(colors[t]) + len(way) - 2 * c + 1,
                                min_cycle)
                continue
            colors[t] = way + [t]
            for k in dd[t]:
                if (not way or k != way[-1]) and (k, colors[t]) not in next_tier:
                    next_tier.append((k, colors[t]))
        tier = next_tier
        next_tier = []

if min_cycle < 1e9:
    print(min_cycle)
else:
    print(-1)

pass

# 1205B
def do():
    n = int(input())
    nums = [int(c) for c in input().split(" ")]
    valid = set()
    for i in range(64):
        count = []
        for j in range(n):
            if (1 << i) & nums[j]:
                count.append(nums[j])
            if len(count) == 3:
                return 3
        if len(count) == 2:
            valid.add(count[0])
            valid.add(count[1])
    # valid won't be that large hahaha at most 64*2
    nv = len(valid)
    valid = list(valid)
    dis = [[float('inf')] * nv for _ in range(nv)]
    for i in range(nv):
        for j in range(nv):
            if i == j:
                dis[i][j] = 0
            elif valid[i] & valid[j]:
                dis[i][j] = 1
    mp = [[_ for _ in dis[i]] for i in range(len(dis))]
    res = nv + 1
    for k in range(nv):
        for i in range(nv):
            if k != i:
                for j in range(nv):
                    if k != j and i != j:
                        res = min(res, dis[i][j] + mp[j][k] + mp[k][i])
        for i in range(nv):
            if k != i:
                for j in range(nv):
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
    return res if res <= nv else -1

print(do())







# 1205B
def do():
    n = int(input())
    nums = [int(c) for c in input().split(" ")]
    valid = set()
    for i in range(64):
        count = []
        for j in range(n):
            if (1 << i) & nums[j]:
                count.append(nums[j])
            if len(count) == 3:
                return 3
        if len(count) == 2:
            valid.add(count[0])
            valid.add(count[1])
    # valid won't be that large hahaha at most 64*2
    nv = len(valid)
    valid = list(valid)
    dis = [[float('inf')] * nv for _ in range(nv)]
    for i in range(nv):
        for j in range(nv):
            if i == j:
                dis[i][j] = 0
            elif valid[i] & valid[j]:
                dis[i][j] = 1
    mp = [[_ for _ in dis[i]] for i in range(len(dis))]
    res = nv + 1
    for k in range(nv):
        for i in range(k):
            for j in range(k):
                if i != j:
                    res = min(res, dis[i][j] + mp[j][k] + mp[k][i])
        for i in range(nv):
            if k != i:
                for j in range(nv):
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
    return res if res <= nv else -1

print(do())







from collections import deque

n=int(input())
s=[int(x) for x in input().split()]
b=[]
mx=-1
for i in range(0,len(s)):
    t=bin(s[i])
    t=t[2:]
    b.append(t)
    mx=max(mx,len(t))

for i in range(0,len(b)):
    b[i]='0'*(mx-len(b[i]))+b[i]

flag=0
L=[]
kk=dict()
for i in range(0,mx):
    c=0
    h=[]
    for j in range(0,len(b)):
        if(b[j][i]=='1'):
            c+=1
            h.append(j)
    if(len(h)==2 and kk.get(tuple(h))==None):
        h=tuple(h)
        L.append(h)
        kk[h]=1
    if(c>2):
        flag=1
        break
#print(L)

if(flag==1):
    print(3)
else:
    temp=1000000007
    for i in range(0,len(L)):

        arr=[]
        for j in range(n):
            s1=[]
            arr.append(s1)

        for j in range(0,len(L)):
            if(j==i):
                src=L[j][0]
                dst=L[j][1]

            else:
                arr[L[j][0]].append(L[j][1])
                arr[L[j][1]].append(L[j][0])

        q=deque()
        q.append((src,0))
        visited=[False]*n
        visited[src]=True

        while(q):

            r=q.popleft()

            visited[r[0]]=True
            if(r[0]==dst):
                temp=min(temp,r[1]+1)
                break

            for j in arr[r[0]]:
                if(visited[j]==False):
                    q.append((j,r[1]+1))


    if(temp==1000000007):
        print(-1)
    else:
        print(temp)

        

        
                
    



class node():
	def __init__(self, v, edges):
		self.value = v
		self.edges = edges
 
n = int(input())
a = [int(i) for i in input().split(" ")]
 
 
def fun(a):
	nodes = {}
	for i in range(60):
		k = 0
		value = 1 << i
		i_edges = set()
		for j in a:
			if value&j > 0:
#                 print(i+1)
				k += 1
				if k > 2:
					del i_edges
					del nodes
					return 3
				i_edges.add(j)
		for j in i_edges:
			if j not in nodes:
				if (i_edges.difference({j})) != 0:
					nodes[j] = node(j,i_edges.difference({j}))
			else:
				nodes[j].edges = nodes[j].edges.union(i_edges.difference({j}))
	return nodes
 
def find_short_path(v1, v2):
	length = 0
	v2 = {v2}
	setic = set()
	set_was = set()
	while (v1 not in setic):
		del setic
		setic = set()
		for i in v2:
			setic = setic.union(nodes[i].edges.difference(set_was))
		set_was = set_was.union(setic)
		if len(setic) == 0:
			del v2
			return 0
		length += 1
		del v2
		v2 = setic.copy()
	del set_was
	del setic
	return length
 
 
nodes = fun(a)
if type(nodes) == int:
	print(3)
else:
	mass = []
	while len(nodes.keys()) != 0:
		# print(type(nodes.keys()))
		i = list(nodes.keys())[0]
		if len(nodes[i].edges) != 0:
			
			first_v = i
			second_v = nodes[first_v].edges.pop()
			nodes[second_v].edges.remove(first_v)
			length = 0
			if len(nodes[first_v].edges) == 0:
				nodes.pop(first_v)
			elif len(nodes[second_v].edges) == 0:
				nodes.pop(second_v)
			else:
				length = find_short_path(first_v, second_v)
	
			if length:
				mass.append(length + 1)
		else:
			nodes.pop(i)
			
	if len(mass) != 0:
		print(min(mass))
	else:
		print(-1)


from sys import stdin
import os
import sys
from atexit import register
from io import BytesIO
import itertools


# sys.stdout = BytesIO()
# register(lambda: os.write(1, sys.stdout.getvalue()))
#
# input = BytesIO(os.read(0, os.fstat(0).st_size)).readline
# if sys.version_info[0] < 3:
#     range = xrange
#     filter = itertools.ifilter
#     map = itertools.imap
#     zip = itertools.izip


def bfs(src, dest, adj):
    visited = [False for _ in range(len(adj))]
    visited[src] = True
    queue = [src]
    i = 1
    while len(queue)>0:
        newq = []
        i += 1
        for node in queue:
            for vertex in adj[node]:
                if node==src and vertex==dest: continue
                if not visited[vertex]:
                    newq.append(vertex)
                    visited[vertex] = True
                    if vertex==dest:
                        return i
        queue = newq
    return -1


def main():
    n = int(input())
    li = list(map(int, input().split()))
    binaries = [0]*n
    adj = [set() for _ in range(n)]
    for index, i in enumerate(li):
        binaries[index] = (bin(i)[2:].zfill(60))
    edges = set()
    #print("Pass 0")
    for j in range(60):
        indexes = []
        for i in range(n):
            if binaries[i][j] == '1':
                indexes.append(i)
                if len(indexes) == 3:
                    print(3)
                    return
        if len(indexes)==2:
            indexes.sort()
            edges.add(tuple(indexes))
            adj[indexes[0]].add(indexes[1])
            adj[indexes[1]].add(indexes[0])
    #print(edges, adj)
    min_cycle = -1
    for li in edges:
        le = bfs(li[0], li[1], adj)
        #print(li, le, min_cycle)
        if min_cycle==-1:
            min_cycle = le
        elif le>-1:
            min_cycle = min(min_cycle, le)
    print(min_cycle)

main()


from collections import defaultdict, deque
import sys

n = int(input())
a = [int(val) for val in input().split()]
a = [val for val in a if val > 0]
n = len(a)

count = defaultdict(list)
for i, val in enumerate(a):
    power = 0
    while val > 0:
        if val % 2 == 1:
            count[power].append(i)
        power +=1
        val = val >> 1

for power, val in list(count.items()):
    if len(val) >= 3:
        print(3)
        return

G = defaultdict(list)
for i in range(n - 1):
    for j in range(i + 1, n):
        if a[i] & a[j] > 0:
            G[i].append(j) 
            G[j].append(i) 

min_cycle = n + 1
for key, _ in list(G.items()):
    qu = deque()
    qu.append((key, 0, None))
    visited = {}
    while len(qu) > 0:
        node = qu.popleft()
        visited[node[0]] = node[1]
        for child in G[node[0]]:
            if child not in visited:
                 qu.append((child, node[1] + 1, node[0]))
            else:
                if node[2] != child:
                    min_cycle = min(min_cycle, visited[child] + node[1] + 1)
if min_cycle == n + 1:
    print(-1)
else:
    print(min_cycle)



import sys
input=sys.stdin.readline
import collections
from collections import defaultdict

visited=set()
mem=[]
G=defaultdict(list)
n=int(input())
l=[int(i) for i  in input().split()]
l=[i for i in l if i>0]

if len(l)>=128 :
    print(3)
elif len(l)<3:
    print(-1)
else:
    for i in range(1,len(l)):
        for j in range(0,i):
            if l[i]&l[j]!=0:
                G[i].append(j)
                G[j].append(i)
    #print(G)
    min_cycle = n + 1
    for key, _ in list(G.items()):
        #print(key,_)
        qu = collections.deque()
        qu.append((key, 0, None))
        visited = {}
        while len(qu) > 0:
            #print(qu,visited)
            node = qu.popleft()
            visited[node[0]] = node[1]
            for child in G[node[0]]:
                if child not in visited:
                     qu.append((child, node[1] + 1, node[0]))
                     #print(qu)
                else:
                    if node[2] != child:
                        min_cycle = min(min_cycle, visited[child] + node[1] + 1)
                        #print(min_cycle,visited[child],node[1])
    if min_cycle == n + 1:
        print(-1)
    else:
        print(min_cycle)

    


from collections import deque


input()
h = [list(bin(int(i)))[2:] for i in input().split()]
sas = min(list(map(len, h)))
ans = 1e9
graf = [[] for _ in range(100000)]
rebra = []
def bfs(assx, sasx):
    q = deque()
    q.append(assx)
    metka = [1 for _ in range(100000)]
    metka[assx] = 0
    dis = [0 for _ in range(100000)]
    while q:
        x = q.popleft()
        for i in graf[x]:
            if i == sasx and x != assx:
                return dis[x] + 2
            if metka[i] and (i != sasx or x != assx):
                metka[i] = 0
                dis[i] = dis[x] + 1
                q.append(i)
    return 0
for i in range(len(h)):
    h[i].reverse()
for i in range(60):
    r = 0
    ass = []
    for j in range(len(h)):
        if len(h[j]) <= i:
            continue
        if int(h[j][i]):
            r += 1
            ass.append(j)
    if r >= 3:
        print(3)
        return
    if len(ass) > 1:
        graf[ass[0]].append(ass[1])
        graf[ass[1]].append(ass[0])
        rebra.append(ass)
for i in rebra:
    g = bfs(i[0], i[1])
    if g:
        ans = min(ans, g)
print(ans if ans != 1e9 else -1)


# -*- coding: utf-8 -*-

import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys
from typing import List

"""
created by shhuan at 2020/1/10 01:32

"""


def shortest_path(u, v, g):
    q = [w for w in g[u] if w != v]
    vis = set(q) | {u}
    d = 0
    while q:
        d += 1
        nq = []
        for w in q:
            if w == v:
                return d
            for x in g[w]:
                if x not in vis:
                    vis.add(x)
                    nq.append(x)
        q = nq

    return float('inf')


def solve(N, A):
    b = 1
    g = collections.defaultdict(list)
    edges = []
    for i in range(64):
        connected = [i for i, v in enumerate(A) if v & b > 0]
        if len(connected) >= 3:
            return 3
        for u in connected:
            for v in connected:
                if u != v:
                    g[u].append(v)
                    edges.append((u, v))
        b <<= 1

    # print(g)
    ans = float('inf')
    for u, v in edges:
        # remove edge u, v
        # print(u, v, shortest_path(u, v, g))
        ans = min(ans, 1 + shortest_path(u, v, g))

    return ans if ans < float('inf') else -1


N = int(input())
A = [int(x) for x in input().split()]
print(solve(N, A))

from collections import deque
inf = int(1e6)


class Graph:
    def __init__(self, n):
        self.n = n
        self.adj = [[] for i in range(n)]
        self.loop = inf

    def add_edge(self, u, v):
        self.adj[u].append(v)
        self.adj[v].append(u)

    def find_loop(self):
        for i in range(n):
            q = deque()
            q.append(i)
            depth = [-1] * n
            depth[i] = 0
            while len(q) > 0:
                u = q.popleft()
                for v in self.adj[u]:
                    if depth[v] >= depth[u]:
                        self.loop = min(self.loop, depth[u] + depth[v] + 1)
                    if depth[v] == -1:
                        depth[v] = depth[u] + 1
                        q.append(v)
        return -1 if self.loop == inf else self.loop


input()
a = list([x for x in map(int, input().split(' ')) if x != 0])
n = len(a)
groups = [0] * 64
for num in a:
    t = '{0:b}'.format(num)
    l = len(t)
    curr = 0
    for i in range(l):
        if t[l - i - 1] == '1':
            groups[i] += 1

loop = -1
for cnt in groups:
    if cnt >= 3:
        loop = 3
        break
if loop == 3:
    print(3)
else:
    g = Graph(n)
    for i in range(n-1):
        for j in range(i + 1, n):
            if a[i] & a[j] != 0:
                g.add_edge(i, j)
    print(g.find_loop())


import sys
import math
from collections import defaultdict

def print_graph(graph):
    for key, values in graph.items():
        [print(key,nodo) for nodo in values]

def BFS(graph, n, start, end):
    #print("==================")
    #print("Partiendo BFS:")
    #print("Nodo Start:", start)
    #print("Nodo end:", end)
    q = [ (start,0) ]
    visited = [False for x in range(n)]
    visited[start] = True
    while (len(q) >0):
        aux = q.pop(0)
        actual = aux[0]
        peso = aux[1]+1
        #print("===========")
        #print("Nodo Actual:",actual)
        for vecino in graph[actual]:
            
            #saltamos el arco base
            if not visited[vecino] and not ((actual == start and end == vecino) or (vecino == start and end == actual)):
                #print("Vecino:",vecino)
                q.append( (vecino, peso) )
                visited[vecino] = True
                if vecino == end:
                    peso+=1
                    #print("PESO FINAL:", peso)
                    return peso
        
        #print("peso hasta el momento:", peso)
    return -1    
 
lines = sys.stdin.read().split("\n")
lines.pop(-1)
#lines = ["50", "65600 17825792 0 288230376285929472 16392 0 0 16896 0 0 10486272 140737488355330 65537 171798691840 571746046443520 0 0 33024 0 2052 36028797155278848 36028805608898560 0 0 562967133290496 0 0 0 146028888064 281474976710660 0 288230376151711746 8388864 0 17180393472 0 0 0 68719476737 34376515584 0 299067162755072 68719478784 0 9007199255789568 140737488879616 9007199254773760 8796093022272 4294967304 17596481011712"]
#lines = ["4", "3 6 28 9"]
n = int(lines[0].strip())
#nodos_int = [  int(x) for x in lines[1].strip().split(" ")]
nodos = [  "{0:b}".format(int(x)).zfill(60) for x in lines[1].strip().split(" ")]
graph = dict()
vertex = []
 
for i in range(n):
    graph[i] = []
    
for bit in range(60):
    count = 0
    q = []
    for index in range(n):
        if nodos[index][bit] =='1':
            count+=1
            q.append(index)
    if count==2:
        graph[q[0]] += [q[1]]
        graph[q[1]] += [q[0]]
        vertex.append([q[0],q[1]])
    if count>2:
        print(3)
        return
 
##print(vertex)
##print(graph)
        
minimo = -1
for index in range(n):
    while len(vertex) > 0:
        a,b = vertex.pop(0)
        peso = BFS(graph, n ,a,b)
        if (peso > 0):
            if minimo == -1:
                minimo = peso
            elif peso<minimo:
                minimo = peso
        
print(minimo)
#print_graph(graph)


n=int(input())
linea = input()
sep = linea.split()
nodos = list(map(int, sep))

conexiones=[list() for i in range(n)]
lista_bits = [list() for i in range(64)]
j = 0
for caquita in nodos:
    if caquita != 0:
        for z in range(64):
            if not (caquita >> z):
                break
            bit = (caquita >> z) & 1
            if bit == 1:
                lista_bits[z].append(j)
    else:
        j -= 1
        n -= 1
    j += 1


# Python3 implementation of the approach 
from sys import maxsize as INT_MAX 
from collections import deque 
  
gr = conexiones
  
# Function to find the length of 
# the shortest cycle in the graph 
def shortest_cycle(n: int) -> int: 
  
    # To store length of the shortest cycle 
    ans = INT_MAX 
  
    # For all vertices 
    for i in range(n): 
  
        # Make distance maximum 
        dist = [int(1e9)] * n 
  
        # Take a imaginary parent 
        par = [-1] * n 
  
        # Distance of source to source is 0 
        dist[i] = 0
        q = deque() 
  
        # Push the source element 
        q.append(i) 
  
        # Continue until queue is not empty 
        while q: 
  
            # Take the first element 
            x = q[0] 
            q.popleft() 
  
            # Traverse for all it's childs 
            for child in gr[x]: 
  
                # If it is not visited yet 
                if dist[child] == int(1e9): 
  
                    # Increase distance by 1 
                    dist[child] = 1 + dist[x] 
  
                    # Change parent 
                    par[child] = x 
  
                    # Push into the queue 
                    q.append(child) 
  
                # If it is already visited 
                elif par[x] != child and par[child] != x: 
                    ans = min(ans, dist[x] + 
                                   dist[child] + 1) 
  
    # If graph contains no cycle 
    if ans == INT_MAX: 
        return -1
  
    # If graph contains cycle 
    else: 
        return ans 

al_menos_tres = False
son_2 = False
for listita in lista_bits:
    if len(listita) >= 3:
        al_menos_tres = True
        break
    elif len(listita) == 2:
        son_2 = True
        x = listita[0]
        y = listita[1]
        gr[x].append(y)
        gr[y].append(x)

if al_menos_tres:
    print(3)
elif not son_2:
    print(-1)
else:
    print(shortest_cycle(n)) 

# This code is contributed by 
# sanjeev2552 



from sys import maxsize as INT_MAX 
from collections import deque 
  
n=int(input())
linea = input()
sep = linea.split()
nodos = list(map(int, sep))
bits= [list() for i in range (64)]
j=0
for s in nodos:
    if s!=0:
        for i in range(64):
            bit=(s >> i) & 1
            if bit==1:
                bits[i].append(j)
    else:
        j-=1
        n-=1
    j+=1
dos= False
ejecucion= True
gr=[list() for i in range (n)]
for k in bits:
    if len(k)==2:
        dos=True
        x= k[0]
        y= k[1]
        gr[x].append(y)
        gr[y].append(x)
    elif len(k) >= 3:
        ejecucion= False
        break
if ejecucion==False: 
    print(3)
elif not dos:
    print(-1)
else:
    # Python3 implementation of the approach 
      
    # Function to find the length of 
    # the shortest cycle in the graph 
    def shortest_cycle(n: int) -> int: 
      
        # To store length of the shortest cycle 
        ans = INT_MAX 
      
        # For all vertices 
        for i in range(n): 
      
            # Make distance maximum 
            dist = [int(1e9)] * n 
      
            # Take a imaginary parent 
            par = [-1] * n 
      
            # Distance of source to source is 0 
            dist[i] = 0
            q = deque() 
      
            # Push the source element 
            q.append(i) 
      
            # Continue until queue is not empty 
            while q: 
      
                # Take the first element 
                x = q[0] 
                q.popleft() 
      
                # Traverse for all it's childs 
                for child in gr[x]: 
      
                    # If it is not visited yet 
                    if dist[child] == int(1e9): 
      
                        # Increase distance by 1 
                        dist[child] = 1 + dist[x] 
      
                        # Change parent 
                        par[child] = x 
      
                        # Push into the queue 
                        q.append(child) 
      
                    # If it is already visited 
                    elif par[x] != child and par[child] != x: 
                        ans = min(ans, dist[x] + 
                                       dist[child] + 1) 
      
        # If graph contains no cycle 
        if ans == INT_MAX: 
            return -1
      
        # If graph contains cycle 
        else: 
            return ans 
      
      
    # Function call 
    print(shortest_cycle(n)) 
      
    # This code is contributed by 
    # sanjeev2552 



import sys
input=sys.stdin.readline
import collections
from collections import defaultdict

visited=set()
mem=[]
G=defaultdict(list)
n=int(input())
l=[int(i) for i  in input().split()]
l=[i for i in l if i>0]

if len(l)>=121 :
    print(3)
elif len(l)<3:
    print(-1)
else:
    for i in range(1,len(l)):
        for j in range(0,i):
            if l[i]&l[j]!=0:
                G[i].append(j)
                G[j].append(i)
    #print(G)
    min_cycle = n + 1
    for key, _ in list(G.items()):
        #print(key,_)
        qu = collections.deque()
        qu.append((key, 0, None))
        visited = {}
        while len(qu) > 0:
            #print(qu,visited)
            node = qu.popleft()
            visited[node[0]] = node[1]
            for child in G[node[0]]:
                if child not in visited:
                     qu.append((child, node[1] + 1, node[0]))
                     #print(qu)
                else:
                    if node[2] != child:
                        min_cycle = min(min_cycle, visited[child] + node[1] + 1)
                        #print(min_cycle,visited[child],node[1])
    if min_cycle == n + 1:
        print(-1)
    else:
        print(min_cycle)

    


from sys import stdin
from collections import deque


INT_MAX = float('inf')
def shortest_cycle(gr): 
  
    # To store length of the shortest cycle 
    ans = INT_MAX 
  
    # For all vertices 
    for i in gr: 
  
        # Make distance maximum 
        dist = {x:int(1e9) for x in gr}
  
        # Take a imaginary parent 
        par = {x:-1 for x in gr} 
  
        # Distance of source to source is 0 
        dist[i] = 0
        q = deque() 
  
        # Push the source element 
        q.append(i) 
  
        # Continue until queue is not empty 
        while q: 
  
            # Take the first element 
            x = q.popleft() 
  
            # Traverse for all it's childs 
            for child in gr[x]: 
  
                # If it is not visited yet 
                if dist[child] == int(1e9): 
  
                    # Increase distance by 1 
                    dist[child] = 1 + dist[x] 
  
                    # Change parent 
                    par[child] = x 
  
                    # Push into the queue 
                    q.append(child) 
  
                # If it is already visited 
                elif par[x] != child and par[child] != x: 
                    ans = min(ans, dist[x] + 
                                   dist[child] + 1) 
  
    # If graph contains no cycle 
    if ans == INT_MAX: 
        return -1
  
    # If graph contains cycle 
    else: 
        return ans
    
n = int(stdin.readline())
a = sorted([int(x) for x in stdin.readline().split()])

if n-a.count(0) > 128:
    print(3)

else:

    l = [[] for x in range(64)]

    mini = False
    for x in a:
        c = 1
        for y in range(64):
            if x & c:
                l[y].append(x)
                if len(l[y]) > 2:
                    mini = True
            c <<= 1

    if mini:
        print(3)
    else:
        minC = float('inf')
        minX = -1
        flatL = set()
        for x in l:
            for y in x:
                flatL.add(y)
        graph = {}
        for x in flatL:
            graph[x] = set()
            for y in flatL:
                if y != x and y&x:
                    graph[x].add(y)
        print(shortest_cycle(graph))
        '''for x in graph:
            visited = {}
            q = deque()
            q.append((x,x,0))
            valid = False
            while q and not valid:
                n,p,d = q.popleft()
                if not n in visited:
                    visited[n] = d
                    for y in graph[n]:
                        if y != p:
                            if y in visited:
                                valid = d+visited[y]
                                break
                            else:
                                q.append((y,n,d+1))
            if valid:
                minC = min(minC,valid)
                minX = x
        if minC != float('inf'):
            print(minC+1)
        else:
            print(-1)'''
        #print(minX)


def solve(n,a):
	B = 60
	bits = [[] for i in range(B)]
	for i in range(n):
		for j in range(B):
			if a[i]&(1<<j):
				bits[j].append(i)

	adj = [[] for i in range(n)]
	for shared in bits:
		if len(shared) >= 3:
			return 3
		elif len(shared)==2:
			u, v = shared
			adj[u].append(v)
			adj[v].append(u)

	vis = [False for u in range(n)]
	dist = [-1 for u in range(n)]
	def shortest_cycle(n,adj,s):
		frontier = [(s,-1)]
		dist[s] = 0
		ptr = 0

		while ptr < len(frontier):
			u, p = frontier[ptr]
			if not vis[u]:
				vis[u] = True
				for v in adj[u]:
					if vis[v] and v != p:
						ans = dist[u]+dist[v]+1
						for u, p in frontier:
							vis[u] = False
							dist[u] = -1
						return ans
					if dist[v]==-1:
						dist[v] = dist[u] + 1
						frontier.append((v,u))	
			ptr += 1

		return 10**18 #INF

	ans = min([shortest_cycle(n,adj,i) for i in range(n)])
	if ans==10**18:
		ans = -1

	return ans

print(solve(int(input()),list(map(int,input().split()))))