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: HARD
Tags: Complete search

Bit manipulation

Graph algorithms

Shortest paths
Skill types: Bit manipulation

Complete search

Starter code:

Solutions:
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 < 1000000000.0:
	print(min_cycle)
else:
	print(-1)
pass


from collections import deque
inf = int(1000000.0)

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(filter(lambda x: x != 0, map(int, input().split(' '))))
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())


n = int(input())
v = list(map(int, input().split()))
a = []
for _v in v:
	if _v:
		a.append(_v)
v = a
n = len(a)
if n > 128:
	print(3)
	exit(0)
ans = 10000000000.0
dis = [[10000000000.0 for _ in range(n)] for __ in range(n)]
dp = [[10000000000.0 for _ in range(n)] for __ in range(n)]
for i in range(n):
	for j in range(n):
		if i != j and v[i] & v[j]:
			dp[i][j] = dis[i][j] = 1
for k in range(n):
	for i in range(n):
		for j in range(n):
			if i != k and j != k and (i != j):
				ans = min(ans, dp[i][j] + dis[i][k] + dis[k][j])
	for i in range(n):
		for j in range(n):
			dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
print([ans, -1][ans == 10000000000.0])


import sys
I = sys.stdin.readline

def rails(x):
	(z, ret) = (1, set())
	while x:
		if x & 1:
			ret.add(z)
		z += 1
		x //= 2
	return ret
n = int(I())
a = map(int, I().split())
a = [i for i in a if i > 0]
n = len(a)
(b, e) = ([[] for i in range(n)], {})
for (i, x) in enumerate(a):
	rs = rails(x)
	for r in rs:
		if not r in e:
			e[r] = []
		e[r].append(i)
		if len(e[r]) > 2:
			print(3)
			sys.exit(0)

def bfs(i, j, k):
	dist = 1
	v = [0] * n
	v[i] = 1
	v[j] = 1
	(q, nq) = ([], [])
	q.append(j)
	while len(q):
		while len(q):
			x = q.pop()
			for y in b[x]:
				if v[y] == 0:
					v[y] = 1
					nq.append(y)
					if y == k:
						return dist
		(q, nq) = (nq, q)
		dist += 1
	return n

def find(i):
	ret = n
	for (j, jj) in enumerate(b[i]):
		for (k, kk) in enumerate(b[i][j + 1:]):
			ret = min(ret, bfs(i, jj, kk))
	return 2 + ret
for v in e.values():
	if len(v) > 1:
		b[v[0]].append(v[1])
		b[v[1]].append(v[0])
ans = min((find(i) for i in range(n)))
print(ans if ans <= n else -1)


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:

	def shortest_cycle(n: int) -> int:
		ans = INT_MAX
		for i in range(n):
			dist = [int(1000000000.0)] * n
			par = [-1] * n
			dist[i] = 0
			q = deque()
			q.append(i)
			while q:
				x = q[0]
				q.popleft()
				for child in gr[x]:
					if dist[child] == int(1000000000.0):
						dist[child] = 1 + dist[x]
						par[child] = x
						q.append(child)
					elif par[x] != child and par[child] != x:
						ans = min(ans, dist[x] + dist[child] + 1)
		if ans == INT_MAX:
			return -1
		else:
			return ans
	print(shortest_cycle(n))


from collections import *
import sys

def ri():
	return int(input())

def rl():
	return list(map(int, input().split()))
n = ri()
aa = rl()
zero_cnt = 0
aa = [value for value in aa if value != 0]
n = len(aa)
edges = set()
graph = defaultdict(list)
bit_shared = defaultdict(list)
for k in range(60):
	for i in range(n):
		if 1 << k & aa[i]:
			bit_shared[k].append(i)
			if len(bit_shared[k]) >= 3:
				print(3)
				sys.exit()
for i in range(n):
	for j in range(i + 1, n):
		if aa[i] & aa[j]:
			if (i, j) not in edges:
				graph[i].append(j)
				graph[j].append(i)
				edges.add((i, j))
ans = 10 ** 5
for i in range(n):
	dist = [int(100000.0)] * n
	dist[i] = 0
	par = [-1] * n
	q = deque([i])
	while q:
		parent = q.popleft()
		for child in graph[parent]:
			if dist[child] == int(100000.0):
				dist[child] = 1 + dist[parent]
				par[child] = parent
				q.append(child)
			elif par[parent] != child and par[child] != parent:
				ans = min(ans, dist[parent] + dist[child] + 1)
if ans == 10 ** 5:
	print(-1)
else:
	print(ans)


from collections import Counter, deque
n = int(input())
arr = list([x for x in map(int, input().strip().split()) if x != 0])
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)


from collections import defaultdict

def extract_min(D, X):
	arg_min = -1
	min_val = float('inf')
	for i in X:
		if D[i] < min_val:
			arg_min = i
			min_val = D[i]
	return arg_min

class Graph:

	def __init__(self, length):
		self.length = length
		self.graph = defaultdict(list)

	def addEdge(self, u, v):
		self.graph[u].append(v)

	def Dijkstra(self, s):
		X = set(range(self.length))
		D = [self.length + 1] * self.length
		P = [None] * self.length
		D[s] = 0
		while X:
			u = extract_min(D, X)
			X.remove(u)
			for v in self.graph[u]:
				if v in X:
					new_dist = D[u] + 1
					if D[v] > new_dist:
						D[v] = new_dist
						P[v] = u
				elif P[u] != v:
					return (True, D[u] + D[v] + 1)
		return (False, self.length)
n = int(input())
nums = list(map(int, input().split(' ')))
a = []
for i in range(n):
	if nums[i] != 0:
		a.append(nums[i])
n = len(a)
if n < 3:
	print(-1)
elif n > 120:
	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.addEdge(i, j)
				G.addEdge(j, i)
	min_len = n + 1
	for i in range(n):
		(has_cycle, length) = G.Dijkstra(i)
		if has_cycle and length < min_len:
			min_len = length
	if min_len == n + 1:
		print(-1)
	else:
		print(min_len)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from sys import maxsize as INT_MAX
from collections import defaultdict, deque

def shortest_cycle(n: int) -> int:
	ans = INT_MAX
	for i in range(n):
		dist = defaultdict(lambda : -1)
		par = defaultdict(lambda : -1)
		dist[i] = 0
		q = deque([])
		q.append(i)
		while q:
			x = q[0]
			q.popleft()
			for child in graph[x]:
				if dist[child] == -1:
					dist[child] = 1 + dist[x]
					par[child] = x
					q.append(child)
				elif par[x] != child and par[child] != x:
					ans = min(ans, dist[x] + dist[child] + 1)
	if ans == INT_MAX:
		return -1
	else:
		return ans
n = int(input())
vals = list(map(int, input().split()))
zer = 0
for s in range(n):
	if vals[s] == 0:
		zer += 1
if n - zer >= 121:
	print(3)
else:
	bit = [[] for s in range(60)]
	info = defaultdict(list)
	for s in range(n):
		num = vals[s]
		for i in range(59, -1, -1):
			if num - 2 ** i >= 0:
				bit[i].append(s)
				num -= 2 ** i
				info[vals[s]].append(i)
	graph = [[] for s in range(n)]
	tracker = [set([]) for s in range(n)]
	for s in range(n):
		for i in info[vals[s]]:
			for b in range(len(bit[i])):
				if bit[i][b] != s and (not bit[i][b] in tracker[s]):
					graph[s].append(bit[i][b])
					tracker[s].add(bit[i][b])
	print(shortest_cycle(n))


from collections import deque
INF = 1000000000
n = int(input())
l = list(map(int, input().split()))
l = [x for x in l if x]
n = len(l)
if n > 120:
	print(3)
else:
	g = [[] for i in range(n)]
	for i in range(n):
		for j in range(n):
			if i != j and l[i] & l[j]:
				g[i].append(j)
	minCycle = INF
	for u1 in range(n):
		for u2 in g[u1]:
			q = deque()
			q.append(u1)
			lenn = [INF for i in range(n)]
			lenn[u1] = 0
			while q:
				fromm = q.popleft()
				for togo in g[fromm]:
					if set([fromm, togo]) == set([u1, u2]):
						continue
					if lenn[togo] == INF:
						lenn[togo] = lenn[fromm] + 1
						q.append(togo)
			minCycle = min(minCycle, lenn[u2] + 1)
	if minCycle == INF:
		print(-1)
	else:
		print(minCycle)


def naiveSolve(n):
	return
from collections import deque

def main():
	n = int(input())
	a = readIntArr()
	setBitCnts = [0] * 60
	newA = []
	for (i, x) in enumerate(a):
		cnt = 0
		for j in range(60):
			if x & 1 << j > 0:
				setBitCnts[j] += 1
				if setBitCnts[j] == 3:
					print(3)
					return
				cnt += 1
		if cnt >= 2:
			newA.append(x)
	a = newA
	n = len(a)
	assert n < 100
	ans = inf
	edges = []
	for i in range(n):
		for j in range(i + 1, n):
			if a[i] & a[j] > 0:
				edges.append([i, j])
	m = len(edges)
	for skip in range(m):
		(u, v) = edges[skip]
		adj = [[] for _ in range(n)]
		for i in range(m):
			if i == skip:
				continue
			(uu, vv) = edges[i]
			adj[uu].append(vv)
			adj[vv].append(uu)
		visited = [False] * n
		visited[u] = True
		q = deque()
		q.append([u, 0])
		while q:
			(node, dist) = q.popleft()
			if node == v:
				ans = min(ans, dist + 1)
				break
			for nex in adj[node]:
				if visited[nex] == False:
					visited[nex] = True
					q.append([nex, dist + 1])
	if ans == inf:
		ans = -1
	print(ans)
	return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(i, j):
	print('? {} {}'.format(i, j))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(' '.join([str(x) for x in ans])))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
from math import gcd, floor, ceil
for _abc in range(1):
	main()


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):
	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
		for vecino in graph[actual]:
			if not visited[vecino] and (not (actual == start and end == vecino or (vecino == start and end == actual))):
				q.append((vecino, peso))
				visited[vecino] = True
				if vecino == end:
					peso += 1
					return peso
	return -1
lines = sys.stdin.read().split('\n')
lines.pop(-1)
n = int(lines[0].strip())
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)
		sys.exit()
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)


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)
	min_cycle = n + 1
	for (key, _) in G.items():
		qu = collections.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]))
				elif 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
n = int(input())
A = list(map(int, input().split()))
X = [0] * 65
for a in A:
	for i in range(65):
		if a & 1 << i != 0:
			X[i] += 1
if max(X) >= 3:
	print(3)
	sys.exit()
B = []
for a in A:
	if a != 0:
		B.append(a)
E = [set() for i in range(len(B))]
for i in range(len(B)):
	for j in range(i + 1, len(B)):
		if B[i] & B[j] != 0:
			E[i].add(j)
			E[j].add(i)
ANS = 1 << 65
from collections import deque
for i in range(len(B)):
	DIS = [-1] * len(B)
	Q = deque([i])
	DIS[i] = 0
	while Q:
		x = Q.popleft()
		for to in E[x]:
			if DIS[to] != -1 and DIS[to] != DIS[x] - 1:
				ANS = min(ANS, DIS[x] + DIS[to] + 1)
			elif DIS[to] == -1:
				DIS[to] = DIS[x] + 1
				Q.append(to)
if ANS == 1 << 65:
	print(-1)
else:
	print(ANS)


import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
L = max(A).bit_length()
ans = -1
graph = [[] for _ in range(N)]
V = []
for l in range(L):
	P = []
	for i in range(N):
		if 1 << l & A[i]:
			P.append(i)
	if len(P) > 2:
		ans = 3
		break
	elif len(P) == 2:
		(p0, p1) = P
		graph[p0].append(p1)
		graph[p1].append(p0)
		V.append(P)

def bfs(s, g):
	a = -1
	q = [s]
	checked = [False] * N
	checked[s] = True
	d = 0
	while q:
		qq = []
		d += 1
		for p in q:
			for np in graph[p]:
				if np == g:
					if d == 1:
						continue
					else:
						return d
				if not checked[np]:
					qq.append(np)
					checked[np] = True
		q = qq
	return -1
if ans == 3:
	print(3)
else:
	ans = 10 ** 9
	for (s, g) in V:
		cycle = bfs(s, g)
		if cycle == -1:
			continue
		ans = min(cycle + 1, ans)
	if ans == 10 ** 9:
		print(-1)
	else:
		print(ans)


from collections import deque

def bfs(graph, root, prune_level):
	n = len(graph)
	level = [-1] * n
	tree = [None] * n
	toVisit = deque([root])
	level[root] = 0
	tree[root] = root
	best_cycle = float('inf')
	best_u = None
	best_v = None
	while toVisit:
		u = toVisit.popleft()
		if level[u] > prune_level:
			break
		for v in graph[u]:
			if tree[u] == v:
				continue
			if level[v] == -1:
				level[v] = level[u] + 1
				toVisit.append(v)
				tree[v] = u
			else:
				prune_level = level[v] - 1
				cycle_len = level[u] + 1 + level[v]
				if cycle_len < best_cycle:
					best_cycle = cycle_len
					best_u = u
					best_v = v
	return (tree, best_cycle, best_u, best_v)

def path(tree, v):
	P = []
	while not P or P[-1] != v:
		P.append(v)
		v = tree[v]
	return P

def shortest_cycle(graph):
	best_cycle = float('inf')
	best_u = None
	best_v = None
	best_tree = None
	V = list(range(len(graph)))
	for root in V:
		(tree, cycle_len, u, v) = bfs(graph, root, best_cycle // 2)
		if cycle_len < best_cycle:
			best_cycle = cycle_len
			best_u = u
			best_v = v
			best_tree = tree
	if best_cycle == float('inf'):
		return []
	Pu = path(best_tree, best_u)
	Pv = path(best_tree, best_v)
	return Pu[::-1] + Pv
n = int(input())
b = list(map(int, input().split()))
a = []
for i in b:
	if i != 0:
		a.append(i)
n = len(a)
if n > 200:
	print(3)
else:
	graph = [[] for i in range(n)]
	for i in range(n):
		for j in range(i + 1, n):
			if a[i] & a[j]:
				graph[i].append(j)
				graph[j].append(i)
	print(len(shortest_cycle(graph)) - 1)


from collections import deque
from collections import defaultdict
n = int(input())
b = list(map(int, input().split()))
ind = [[] for i in range(61)]
l = [0] * 61
for i in range(n):
	for mask in range(61):
		if b[i] & 1 << mask:
			ind[mask].append(i + 1)
			l[mask] += 1
adj = [[] for i in range(n + 1)]
poss = 0
for mask in range(61):
	if l[mask] < 2:
		pass
	elif l[mask] == 2:
		adj[ind[mask][0]].append(ind[mask][1])
		adj[ind[mask][1]].append(ind[mask][0])
	else:
		poss = 1
		break
if poss:
	print(3)
else:
	for i in range(1, n + 1):
		adj[i] = list(set(adj[i]))
	vis = [0] * (n + 1)
	i = 1
	shortest = float('inf')
	while i <= n:
		if not vis[i]:
			poss = []
			q = deque()
			q.append(i)
			vis[i] = 1
			poss.append(i)
			while q:
				curr = q.popleft()
				for j in adj[curr]:
					if vis[j]:
						pass
					else:
						vis[j] = 1
						q.append(j)
						poss.append(j)
			for v in poss:
				q = deque()
				q.append(v)
				d = defaultdict(lambda : float('inf'))
				d[v] = 0
				par = defaultdict(lambda : -1)
				q.append(v)
				while q:
					curr = q.popleft()
					for j in adj[curr]:
						if d[j] != float('inf'):
							if par[curr] != j and par[j] != curr:
								shortest = min(shortest, d[curr] + d[j] + 1)
						else:
							d[j] = d[curr] + 1
							par[j] = curr
							q.append(j)
		i += 1
	if shortest == float('inf'):
		print(-1)
	else:
		print(shortest)


from collections import deque
input()
h = [list(bin(int(i)))[2:] for i in input().split()]
sas = min(map(len, h))
ans = 1000000000.0
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)
		exit()
	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 != 1000000000.0 else -1)


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 sys import stdin
import os
import sys
from atexit import register
from io import BytesIO
import itertools

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()
	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])
	min_cycle = -1
	for li in edges:
		le = bfs(li[0], li[1], adj)
		if min_cycle == -1:
			min_cycle = le
		elif le > -1:
			min_cycle = min(min_cycle, le)
	print(min_cycle)
main()


from collections import deque
from copy import deepcopy

def compress(L):
	L2 = list(set(L))
	L2.sort()
	C = {v: k for (k, v) in enumerate(L2)}
	return (L2, C)

def bfs(E, u, v):
	inf = 10 ** 9
	Edge = deepcopy(E)
	Edge[u].remove(v)
	Edge[v].remove(u)
	Q = deque([u])
	used = set([u])
	dist = [inf] * N
	dist[u] = 0
	while Q:
		vn = Q.pop()
		for vf in Edge[vn]:
			if vf not in used:
				used.add(vf)
				Q.appendleft(vf)
				dist[vf] = dist[vn] + 1
	return dist
N = int(input())
A = list(map(int, input().split()))
cnt = [0] * 61
D = [[] for _ in range(61)]
ans = 3
for i in range(N):
	a = A[i]
	for j in range(61):
		if a & 1:
			cnt[j] += 1
			D[j].append(i)
		a >>= 1
		if cnt[j] > 2:
			break
	else:
		continue
	break
else:
	inf = 10 ** 9
	ver = set()
	for d in D:
		if len(d) != 2:
			continue
		(a, b) = d
		ver.add(a)
		ver.add(b)
	n = len(ver)
	V = list(ver)
	(_, tr) = compress(V)
	an = inf
	Edge = [[] for _ in range(n)]
	for d in D:
		if len(d) != 2:
			continue
		(a, b) = d
		(a, b) = (tr[a], tr[b])
		Edge[a].append(b)
		Edge[b].append(a)
	D = [(tr[d[0]], tr[d[1]]) for d in D if len(d) == 2]
	Edge = [list(set(e)) for e in Edge]
	for d in D:
		(u, v) = d
		distu = bfs(Edge, u, v)
		distv = bfs(Edge, v, u)
		an = min(an, min((1 + distu[i] + distv[i] for i in range(n))))
	if an > 10 ** 8:
		ans = -1
	else:
		ans = an
print(ans)


import sys
n = int(input())
dat = [int(i) for i in input().split()]
data = [i for i in dat if i != 0]
n = len(data)
dic = {}
for d in data:
	if d in dic:
		dic[d] += 1
	else:
		dic[d] = 1
keys = list(dic.keys())
if len(keys) != len(data):
	if len(data) > 200:
		print(3)
		sys.exit()
	else:
		data2 = []
		for i in range(len(keys)):
			k = keys[i]
			if k != 0:
				if dic[k] == 2:
					for j in range(len(keys)):
						if k & keys[j] and i != j:
							print(3)
							sys.exit()
				elif dic[k] > 2:
					print(3)
					sys.exit()
				else:
					data2.append(k)
		data = data2
		n = len(data)
inf = 1 << 10
if n > 100:
	print(3)
	sys.exit()

def bfs(a):
	layer = {a}
	parent = {a: -1}
	cnt = 0
	while len(layer) > 0:
		cnt += 1
		new = set()
		ret = -1
		for l in layer:
			for v in data:
				if l & v and v != l and (parent[l] != v):
					if v in layer:
						return 2 * cnt - 1
					elif v in new:
						ret = 2 * cnt
					parent[v] = l
					new.add(v)
		layer = new
		if ret != -1:
			return ret
	return inf
ans = inf
for d in data:
	a2 = bfs(d)
	if a2 == inf:
		continue
	elif a2 == 3:
		print(3)
		sys.exit()
	elif a2 < ans:
		ans = a2
if ans == inf:
	print(-1)
else:
	print(ans)


from collections import deque
bits = [0] * 64
n = int(input())
data = list(filter(lambda x: x != 0, map(int, input().split())))
n = len(data)
if n == 0:
	print(-1)
	exit(0)
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)
		exit(0)
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(map(bfs, range(n)))
print(answer if answer <= n else -1)


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 count.items():
	if len(val) >= 3:
		print(3)
		sys.exit(0)
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 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]))
			elif 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 math
edges = []
result = -1

def dfs(ns, path, visited, last, now):
	visited[now] = True
	global edges
	for i in edges[now]:
		if i == last:
			continue
		if i in path:
			new_result = len(path) - path.index(i)
			global result
			if result < 0 or result > new_result:
				result = new_result
			continue
		dfs(ns, path + [i], visited, now, i)

def solve():
	n = int(input())
	ns = [int(x) for x in input().split()]
	global edges
	edges = []
	for i in range(n):
		edges.append(list())
	p = 1
	for i in range(70):
		s = []
		for t in range(n):
			if ns[t] & p != 0:
				s.append(t)
				if len(s) >= 3:
					return 3
		if len(s) == 2:
			edges[s[0]].append(s[1])
			edges[s[1]].append(s[0])
		p <<= 1
	global result
	result = -1
	visited = [False] * n
	for start in range(n):
		if not visited[start]:
			dfs(ns, [start], visited, -1, start)
	return result

def main():
	print(solve())
main()


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
from sys import maxsize as INT_MAX
from collections import deque
gr = conexiones

def shortest_cycle(n: int) -> int:
	ans = INT_MAX
	for i in range(n):
		dist = [int(1000000000.0)] * n
		par = [-1] * n
		dist[i] = 0
		q = deque()
		q.append(i)
		while q:
			x = q[0]
			q.popleft()
			for child in gr[x]:
				if dist[child] == int(1000000000.0):
					dist[child] = 1 + dist[x]
					par[child] = x
					q.append(child)
				elif par[x] != child and par[child] != x:
					ans = min(ans, dist[x] + dist[child] + 1)
	if ans == INT_MAX:
		return -1
	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))


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))
n = inp()
a = inpl()
b = []
for x in a:
	if x != 0:
		b.append(x)
n = len(b)
if n > 200:
	print(3)
	quit()
if n == 0:
	print(-1)
	quit()
g = [[] for _ in range(n)]
for i in range(n):
	for j in range(i + 1, n):
		for k in range(65):
			if (b[i] >> k) % 2 and (b[j] >> k) % 2:
				g[i].append(j)
				g[j].append(i)
				break
res = INF
for i in range(n):
	dist = [INF] * n
	dist[i] = 0
	fro = [-1] * n
	q = deque()
	q.append(i)
	while q:
		nv = q.popleft()
		for v in g[nv]:
			if fro[nv] == v:
				continue
			if dist[v] != INF:
				if fro[v] == fro[nv]:
					res = 3
				else:
					res = min(res, dist[nv] + dist[v] + 1)
			else:
				fro[v] = nv
				dist[v] = dist[nv] + 1
				q.append(v)
print(res if res != INF else -1)


import os
import sys
from io import BytesIO, IOBase
from collections import deque

def main():
	n = int(input())
	arr = [i for i in map(int, input().split()) if i]
	n = len(arr)
	if n > 120:
		print(3)
		exit()
	graph = [0] * 60
	for i in arr:
		j = 0
		while i:
			graph[j] += i & 1
			i >>= 1
			j += 1
	if max(graph) >= 3:
		print(3)
		exit()
	final = [[] for _ in range(n)]
	for i in range(n):
		for j in range(i + 1, n):
			if arr[i] & arr[j]:
				final[i].append(j)
				final[j].append(i)
	ans = 300
	for i in range(n):
		dist = [300] * n
		parent = [-1] * n
		q = deque([i])
		dist[i] = 0
		while q:
			z = q.popleft()
			for child in final[z]:
				if dist[child] == 300:
					dist[child] = dist[z] + 1
					parent[child] = z
					q.append(child)
				elif parent[z] != child and parent[child] != z:
					ans = min(ans, dist[z] + dist[child] + 1)
	if ans == 300:
		print(-1)
	else:
		print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
s = [list() for i in range(0, 61)]
v = []
for _v in a:
	if _v:
		v.append(_v)
a = v
n = len(v)
if n > 128:
	print(3)
	exit()
for i in range(0, len(a)):
	for j in range(0, 61):
		if a[i] & 1 << j != 0:
			s[j].append(a[i])
			if len(s[j]) > 2:
				print(3)
				exit()
ans = 10000000000.0
dis = [[10000000000.0 for _ in range(n)] for __ in range(n)]
dp = [[10000000000.0 for _ in range(n)] for __ in range(n)]
for i in range(n):
	for j in range(n):
		if i != j and a[i] & a[j]:
			dp[i][j] = dis[i][j] = 1
for k in range(n):
	for i in range(k):
		for j in range(i + 1, k):
			ans = min(ans, dp[i][j] + dis[i][k] + dis[k][j])
	for i in range(n):
		for j in range(n):
			dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
print([ans, -1][ans == 10000000000.0])


n = int(input())
a = []
for x in input().split():
	x = int(x)
	if x:
		a.append(x)
n = len(a)
edges = set()
for d in range(64):
	p = 1 << d
	c = []
	for i in range(n):
		x = a[i]
		if x & p:
			c.append(i)
			if len(c) > 2:
				import sys
				print(3)
				sys.exit()
	if len(c) == 2:
		edges.add((c[0], c[1]))
m = n + 1
adj = [[][:] for _ in range(n)]
for (u, v) in edges:
	adj[u].append(v)
	adj[v].append(u)
from collections import deque
for r in range(n):
	v = [False] * n
	p = [-1] * n
	d = [n + 1] * n
	d[r] = 0
	s = deque([r])
	while len(s):
		h = s.popleft()
		v[h] = True
		for c in adj[h]:
			if p[h] == c:
				continue
			elif v[c]:
				m = min(d[h] + 1 + d[c], m)
			else:
				d[c] = d[h] + 1
				v[c] = True
				p[c] = h
				s.append(c)
if m == n + 1:
	m = -1
print(m)


import math
n = int(input())
ns = {}
a = list(map(int, input().split()))
for v in a:
	if v == 0:
		continue
	if v in ns:
		ns[v] += 1
		if ns[v] >= 3:
			print(3)
			exit(0)
	else:
		ns[v] = 1
a = [v for v in ns]
n = len(a)
MAX_A = 10 ** 18
n_bits = math.ceil(math.log(MAX_A, 2)) + 1
if n > n_bits * 3:
	print(3)
	exit(0)
comp = [[] for _ in range(n_bits)]
G = {}

def add(v):
	G[v] = set()
	(v2, i) = (v, 0)
	while v2 != 0:
		if v2 % 2 == 1:
			comp[i].append(v)
		v2 //= 2
		i += 1
for v in a:
	add(v)
for c in comp:
	if len(c) >= 3:
		print(3)
		exit(0)
	elif len(c) == 2:
		(v, w) = c
		G[v].add(w)
		G[w].add(v)
for v in a:
	if ns[v] == 2 and len(G[v]) > 0:
		print(3)
		exit(0)
res = -1
for u in a:
	level = {v: -1 for v in a}
	level[u] = 0
	l = [u]
	i = 0
	while len(l) > 0 and (res < 0 or 2 * i < res):
		l2 = []
		for v in l:
			for w in G[v]:
				if level[w] == -1:
					l2.append(w)
					level[w] = i + 1
				elif level[w] >= i:
					res = min(res, i + 1 + level[w]) if res > 0 else i + 1 + level[w]
		l = l2
		i += 1
print(res)


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
	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()))))


_ = int(input())
v = list(filter(lambda x: x > 0, list(map(int, input().split()))))
n = len(v)
if n > 128:
	print(3)
	exit(0)
ans = 10000000000.0
dis = [[10000000000.0 for _ in range(n)] for __ in range(n)]
dp = [[10000000000.0 for _ in range(n)] for __ in range(n)]
for i in range(n):
	for j in range(n):
		if i != j and v[i] & v[j]:
			dp[i][j] = dis[i][j] = 1
for k in range(n):
	for i in range(n):
		for j in range(n):
			if i != k and j != k and (i != j):
				ans = min(ans, dp[i][j] + dis[i][k] + dis[k][j])
	for i in range(n):
		for j in range(n):
			dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
print([ans, -1][ans == 10000000000.0])


import sys
from sys import maxsize as INT_MAX
from collections import deque, defaultdict
gr = defaultdict(list)

def add_edge(x: int, y: int) -> None:
	global gr
	gr[x].append(y)
	gr[y].append(x)

def shortest_cycle(n: int) -> int:
	ans = INT_MAX
	for i in range(n):
		dist = [int(1000000000.0)] * n
		par = [-1] * n
		dist[i] = 0
		q = deque()
		q.append(i)
		while q:
			x = q[0]
			q.popleft()
			for child in gr[x]:
				if dist[child] == int(1000000000.0):
					dist[child] = 1 + dist[x]
					par[child] = x
					q.append(child)
				elif par[x] != child and par[child] != x:
					ans = min(ans, dist[x] + dist[child] + 1)
	if ans == INT_MAX:
		return -1
	else:
		return ans
n = int(input())
l = list(map(int, input().split()))
l.sort()
l = deque(l)
while l[0] == 0:
	l.popleft()
	if l == deque([]):
		print(-1)
		sys.exit()
n = len(l)
if sum(l) == 0:
	print(-1)
	sys.exit()
if len(set(l)) >= 120:
	print(3)
	sys.exit()
d = defaultdict(int)
for i in range(n):
	w = bin(l[i])[2:]
	for j in range(len(w)):
		d[len(w) - j] += int(w[j])
if max(d.values()) >= 3:
	print(3)
	sys.exit()
for i in range(n):
	for j in range(i + 1, n):
		if l[i] & l[j] != 0:
			add_edge(i, j)
print(shortest_cycle(n))


def divisors(M):
	d = []
	i = 1
	while M >= i ** 2:
		if M % i == 0:
			d.append(i)
			if i ** 2 != M:
				d.append(M // i)
		i = i + 1
	return d

def popcount(x):
	x = x - (x >> 1 & 1431655765)
	x = (x & 858993459) + (x >> 2 & 858993459)
	x = x + (x >> 4) & 252645135
	x = x + (x >> 8)
	x = x + (x >> 16)
	return x & 127

def eratosthenes(n):
	res = [0 for i in range(n + 1)]
	prime = set([])
	for i in range(2, n + 1):
		if not res[i]:
			prime.add(i)
			for j in range(1, n // i + 1):
				res[i * j] = 1
	return prime

def factorization(n):
	res = []
	for p in prime:
		if n % p == 0:
			while n % p == 0:
				n //= p
			res.append(p)
	if n != 1:
		res.append(n)
	return res

def euler_phi(n):
	res = n
	for x in range(2, n + 1):
		if x ** 2 > n:
			break
		if n % x == 0:
			res = res // x * (x - 1)
			while n % x == 0:
				n //= x
	if n != 1:
		res = res // n * (n - 1)
	return res

def ind(b, n):
	res = 0
	while n % b == 0:
		res += 1
		n //= b
	return res

def isPrimeMR(n):
	d = n - 1
	d = d // (d & -d)
	L = [2, 3, 5, 7, 11, 13, 17]
	for a in L:
		t = d
		y = pow(a, t, n)
		if y == 1:
			continue
		while y != n - 1:
			y = y * y % n
			if y == 1 or t == n - 1:
				return 0
			t <<= 1
	return 1

def findFactorRho(n):
	from math import gcd
	m = 1 << n.bit_length() // 8
	for c in range(1, 99):
		f = lambda x: (x * x + c) % n
		(y, r, q, g) = (2, 1, 1, 1)
		while g == 1:
			x = y
			for i in range(r):
				y = f(y)
			k = 0
			while k < r and g == 1:
				ys = y
				for i in range(min(m, r - k)):
					y = f(y)
					q = q * abs(x - y) % n
				g = gcd(q, n)
				k += m
			r <<= 1
		if g == n:
			g = 1
			while g == 1:
				ys = f(ys)
				g = gcd(abs(x - ys), n)
		if g < n:
			if isPrimeMR(g):
				return g
			elif isPrimeMR(n // g):
				return n // g
			return findFactorRho(g)

def primeFactor(n):
	i = 2
	ret = {}
	rhoFlg = 0
	while i * i <= n:
		k = 0
		while n % i == 0:
			n //= i
			k += 1
		if k:
			ret[i] = k
		i += 1 + i % 2
		if i == 101 and n >= 2 ** 20:
			while n > 1:
				if isPrimeMR(n):
					(ret[n], n) = (1, 1)
				else:
					rhoFlg = 1
					j = findFactorRho(n)
					k = 0
					while n % j == 0:
						n //= j
						k += 1
					ret[j] = k
	if n > 1:
		ret[n] = 1
	if rhoFlg:
		ret = {x: ret[x] for x in sorted(ret)}
	return ret

def divisors(n):
	res = [1]
	prime = primeFactor(n)
	for p in prime:
		newres = []
		for d in res:
			for j in range(prime[p] + 1):
				newres.append(d * p ** j)
		res = newres
	res.sort()
	return res

def xorfactorial(num):
	if num == 0:
		return 0
	elif num == 1:
		return 1
	elif num == 2:
		return 3
	elif num == 3:
		return 0
	else:
		x = baseorder(num)
		return 2 ** x * ((num - 2 ** x + 1) % 2) + function(num - 2 ** x)

def xorconv(n, X, Y):
	if n == 0:
		res = [X[0] * Y[0] % mod]
		return res
	x = [X[i] + X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	y = [Y[i] + Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	z = [X[i] - X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	w = [Y[i] - Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	res1 = xorconv(n - 1, x, y)
	res2 = xorconv(n - 1, z, w)
	former = [(res1[i] + res2[i]) * inv for i in range(2 ** (n - 1))]
	latter = [(res1[i] - res2[i]) * inv for i in range(2 ** (n - 1))]
	former = list(map(lambda x: x % mod, former))
	latter = list(map(lambda x: x % mod, latter))
	return former + latter

def merge_sort(A, B):
	(pos_A, pos_B) = (0, 0)
	(n, m) = (len(A), len(B))
	res = []
	while pos_A < n and pos_B < m:
		(a, b) = (A[pos_A], B[pos_B])
		if a < b:
			res.append(a)
			pos_A += 1
		else:
			res.append(b)
			pos_B += 1
	res += A[pos_A:]
	res += B[pos_B:]
	return res

class UnionFindVerSize:

	def __init__(self, N):
		self._parent = [n for n in range(0, N)]
		self._size = [1] * N
		self.group = N

	def find_root(self, x):
		if self._parent[x] == x:
			return x
		self._parent[x] = self.find_root(self._parent[x])
		stack = [x]
		while self._parent[stack[-1]] != stack[-1]:
			stack.append(self._parent[stack[-1]])
		for v in stack:
			self._parent[v] = stack[-1]
		return self._parent[x]

	def unite(self, x, y):
		gx = self.find_root(x)
		gy = self.find_root(y)
		if gx == gy:
			return
		self.group -= 1
		if self._size[gx] < self._size[gy]:
			self._parent[gx] = gy
			self._size[gy] += self._size[gx]
		else:
			self._parent[gy] = gx
			self._size[gx] += self._size[gy]

	def get_size(self, x):
		return self._size[self.find_root(x)]

	def is_same_group(self, x, y):
		return self.find_root(x) == self.find_root(y)

class WeightedUnionFind:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.size = [1 for i in range(N)]
		self.val = [0 for i in range(N)]
		self.flag = True
		self.edge = [[] for i in range(N)]

	def dfs(self, v, pv):
		stack = [(v, pv)]
		new_parent = self.parent[pv]
		while stack:
			(v, pv) = stack.pop()
			self.parent[v] = new_parent
			for (nv, w) in self.edge[v]:
				if nv != pv:
					self.val[nv] = self.val[v] + w
					stack.append((nv, v))

	def unite(self, x, y, w):
		if not self.flag:
			return
		if self.parent[x] == self.parent[y]:
			self.flag = self.val[x] - self.val[y] == w
			return
		if self.size[self.parent[x]] > self.size[self.parent[y]]:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[x] += self.size[y]
			self.val[y] = self.val[x] - w
			self.dfs(y, x)
		else:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[y] += self.size[x]
			self.val[x] = self.val[y] + w
			self.dfs(x, y)

class Dijkstra:

	class Edge:

		def __init__(self, _to, _cost):
			self.to = _to
			self.cost = _cost

	def __init__(self, V):
		self.G = [[] for i in range(V)]
		self._E = 0
		self._V = V

	@property
	def E(self):
		return self._E

	@property
	def V(self):
		return self._V

	def add_edge(self, _from, _to, _cost):
		self.G[_from].append(self.Edge(_to, _cost))
		self._E += 1

	def shortest_path(self, s):
		import heapq
		que = []
		d = [10 ** 15] * self.V
		d[s] = 0
		heapq.heappush(que, (0, s))
		while len(que) != 0:
			(cost, v) = heapq.heappop(que)
			if d[v] < cost:
				continue
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if d[e.to] > d[v] + e.cost:
					d[e.to] = d[v] + e.cost
					heapq.heappush(que, (d[e.to], e.to))
		return d

def Z_algorithm(s):
	N = len(s)
	Z_alg = [0] * N
	Z_alg[0] = N
	i = 1
	j = 0
	while i < N:
		while i + j < N and s[j] == s[i + j]:
			j += 1
		Z_alg[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < N and k + Z_alg[k] < j:
			Z_alg[i + k] = Z_alg[k]
			k += 1
		i += k
		j -= k
	return Z_alg

class BIT:

	def __init__(self, n, mod=0):
		self.BIT = [0] * (n + 1)
		self.num = n
		self.mod = mod

	def query(self, idx):
		res_sum = 0
		mod = self.mod
		while idx > 0:
			res_sum += self.BIT[idx]
			if mod:
				res_sum %= mod
			idx -= idx & -idx
		return res_sum

	def update(self, idx, x):
		mod = self.mod
		while idx <= self.num:
			self.BIT[idx] += x
			if mod:
				self.BIT[idx] %= mod
			idx += idx & -idx
		return

class dancinglink:

	def __init__(self, n, debug=False):
		self.n = n
		self.debug = debug
		self._left = [i - 1 for i in range(n)]
		self._right = [i + 1 for i in range(n)]
		self.exist = [True for i in range(n)]

	def pop(self, k):
		if self.debug:
			assert self.exist[k]
		L = self._left[k]
		R = self._right[k]
		if L != -1:
			if R != self.n:
				(self._right[L], self._left[R]) = (R, L)
			else:
				self._right[L] = self.n
		elif R != self.n:
			self._left[R] = -1
		self.exist[k] = False

	def left(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._left[res]
			if res == -1:
				break
			k -= 1
		return res

	def right(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._right[res]
			if res == self.n:
				break
			k -= 1
		return res

class SparseTable:

	def __init__(self, A, merge_func, ide_ele):
		N = len(A)
		n = N.bit_length()
		self.table = [[ide_ele for i in range(n)] for i in range(N)]
		self.merge_func = merge_func
		for i in range(N):
			self.table[i][0] = A[i]
		for j in range(1, n):
			for i in range(0, N - 2 ** j + 1):
				f = self.table[i][j - 1]
				s = self.table[i + 2 ** (j - 1)][j - 1]
				self.table[i][j] = self.merge_func(f, s)

	def query(self, s, t):
		b = t - s + 1
		m = b.bit_length() - 1
		return self.merge_func(self.table[s][m], self.table[t - 2 ** m + 1][m])

class BinaryTrie:

	class node:

		def __init__(self, val):
			self.left = None
			self.right = None
			self.max = val

	def __init__(self):
		self.root = self.node(-10 ** 15)

	def append(self, key, val):
		pos = self.root
		for i in range(29, -1, -1):
			pos.max = max(pos.max, val)
			if key >> i & 1:
				if pos.right is None:
					pos.right = self.node(val)
					pos = pos.right
				else:
					pos = pos.right
			elif pos.left is None:
				pos.left = self.node(val)
				pos = pos.left
			else:
				pos = pos.left
		pos.max = max(pos.max, val)

	def search(self, M, xor):
		res = -10 ** 15
		pos = self.root
		for i in range(29, -1, -1):
			if pos is None:
				break
			if M >> i & 1:
				if xor >> i & 1:
					if pos.right:
						res = max(res, pos.right.max)
					pos = pos.left
				else:
					if pos.left:
						res = max(res, pos.left.max)
					pos = pos.right
			elif xor >> i & 1:
				pos = pos.right
			else:
				pos = pos.left
		if pos:
			res = max(res, pos.max)
		return res

def solveequation(edge, ans, n, m):
	x = [0] * m
	used = [False] * n
	for v in range(n):
		if used[v]:
			continue
		y = dfs(v)
		if y != 0:
			return False
	return x

	def dfs(v):
		used[v] = True
		r = ans[v]
		for (to, dire, id) in edge[v]:
			if used[to]:
				continue
			y = dfs(to)
			if dire == -1:
				x[id] = y
			else:
				x[id] = -y
			r += y
		return r

class SegmentTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		self.size = n
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, l, r):
		if r == self.size:
			r = self.num
		res = self.ide_ele
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				res = self.segfunc(res, self.tree[r - 1])
			l >>= 1
			r >>= 1
		return res

	def bisect_l(self, l, r, x):
		l += self.num
		r += self.num
		Lmin = -1
		Rmin = -1
		while l < r:
			if l & 1:
				if self.tree[l] <= x and Lmin == -1:
					Lmin = l
				l += 1
			if r & 1:
				if self.tree[r - 1] <= x:
					Rmin = r - 1
			l >>= 1
			r >>= 1
		if Lmin != -1:
			pos = Lmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		elif Rmin != -1:
			pos = Rmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		else:
			return -1
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import gcd, log
input = lambda : sys.stdin.readline().rstrip()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
n = int(input())
A = li()
A = [a for a in A if a != 0]
n = len(A)
a = A
if n >= 180:
	exit(print(3))
Edge = []
for i in range(n):
	for j in range(n):
		if i != j and a[i] & a[j]:
			Edge.append((i, j))
res = 10 ** 8
for start in range(n):
	dist = [10 ** 8 for i in range(n)]
	dist[start] = 0
	deq = deque([start])
	ban = set()
	while deq:
		v = deq.popleft()
		for nv in range(n):
			if v == nv or a[v] & a[nv] == 0:
				continue
			if dist[nv] > dist[v] + 1:
				ban.add((v, nv))
				ban.add((nv, v))
				dist[nv] = dist[v] + 1
				deq.append(nv)
	for (i, j) in Edge:
		if i != start and j != start and ((i, j) not in ban):
			res = min(res, dist[i] + dist[j] + 1)
if res == 10 ** 8:
	print(-1)
else:
	print(res)


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)
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
input = sys.stdin.readline
from collections import deque

class Graph(object):

	def __init__(self, n, d):
		self.n = n
		self.graph = [[] for i in range(n)]
		self.parent = [-1 for i in range(n)]
		self.directed = d

	def addEdge(self, x, y):
		self.graph[x].append(y)
		if not self.directed:
			self.graph[y].append(x)

	def bfs(self, root):
		queue = [root]
		queue = deque(queue)
		vis = [0] * self.n
		while len(queue) != 0:
			element = queue.popleft()
			vis[element] = 1
			for i in self.graph[element]:
				if vis[i] == 0:
					queue.append(i)
					self.parent[i] = element
					vis[i] = 1

	def dfs(self, root):
		ans = [0] * n
		stack = [root]
		vis = [0] * self.n
		stack2 = []
		while len(stack) != 0:
			element = stack.pop()
			if vis[element]:
				continue
			vis[element] = 1
			stack2.append(element)
			for i in self.graph[element]:
				if vis[i] == 0:
					self.parent[i] = element
					stack.append(i)
		while len(stack2) != 0:
			element = stack2.pop()
			m = 0
			for i in self.graph[element]:
				if i != self.parent[element]:
					m += ans[i]
			ans[element] = m
		return ans

	def shortestpath(self, source, dest):
		self.bfs(source)
		path = [dest]
		while self.parent[path[-1]] != -1:
			path.append(parent[path[-1]])
		return path[::-1]

	def detect_cycle(self):
		indeg = [0] * self.n
		for i in range(self.n):
			for j in self.graph[i]:
				indeg[j] += 1
		q = deque()
		vis = 0
		for i in range(self.n):
			if indeg[i] == 0:
				q.append(i)
		while len(q) != 0:
			e = q.popleft()
			vis += 1
			for i in self.graph[e]:
				indeg[i] -= 1
				if indeg[i] == 0:
					q.append(i)
		if vis != self.n:
			return True
		return False

	def reroot(self, root, ans):
		stack = [root]
		vis = [0] * n
		while len(stack) != 0:
			e = stack[-1]
			if vis[e]:
				stack.pop()
				continue
			vis[e] = 1
			for i in graph[e]:
				if not vis[e]:
					stack.append(i)
			if self.parent[e] == -1:
				continue

	def eulertour(self, root):
		stack = [root]
		t = []
		while len(stack) != 0:
			element = stack[-1]
			if vis[element]:
				t.append(stack.pop())
				continue
			t.append(element)
			vis[element] = 1
			for i in self.graph[element]:
				if not vis[i]:
					stack.append(i)
		return t

	def check(self, root):
		q = [root]
		q = deque(q)
		vis = [0] * self.n
		dist = {root: 0}
		vis[root] = 1
		self.parent = [-1] * n
		ans = 10 ** 18
		while q:
			e = q.popleft()
			for i in self.graph[e]:
				if i not in dist:
					dist[i] = dist[e] + 1
					self.parent[i] = e
					q.append(i)
				elif self.parent[e] != i and self.parent[i] != e:
					ans = min(ans, dist[e] + dist[i] + 1)
		return ans

	def cycle(self):
		ans = 10 ** 18
		for i in range(n):
			x = self.check(i)
			ans = min(ans, x)
		return ans
n = int(input())
b = list(map(int, input().split()))
a = [b[i] for i in range(n) if b[i] != 0]
n = len(a)
if n == 0:
	print(-1)
	exit()
o = []
for i in range(n):
	if a[i] % 2:
		o.append(i)
if len(o) >= 3:
	print(3)
	exit()
count = [0] * 64
for i in a:
	x = bin(i)[2:]
	x = '0' * (64 - len(x)) + x
	for j in range(64):
		if x[j] == '1':
			count[j] += 1
for i in count:
	if i >= 3:
		print(3)
		exit()
g = Graph(n, False)
for i in range(n):
	for j in range(i + 1, n):
		if a[i] & a[j] != 0:
			g.addEdge(i, j)
			root = i
t = [0] * n
ans = g.cycle()
if ans == 10 ** 18:
	print(-1)
else:
	print(ans)


import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
flag = False
for i in range(61):
	cnt = 0
	for j in range(n):
		if a[j] << i & 1:
			cnt += 1
	if cnt >= 3:
		flag = True
if flag:
	print(3)
	exit()
nodes = []
for i in range(n):
	if a[i] != 0:
		nodes.append(a[i])
g = [set() for i in range(len(nodes))]
for i in range(len(nodes)):
	for j in range(i + 1, len(nodes)):
		if nodes[i] & nodes[j] != 0:
			g[i].add(j)
			g[j].add(i)
ans = 10 ** 18
for i in range(len(nodes)):
	dis = [-1] * len(nodes)
	dq = deque()
	dq.append(i)
	dis[i] = 0
	while dq:
		ver = dq.popleft()
		for to in g[ver]:
			if dis[to] != -1 and dis[to] != dis[ver] - 1:
				ans = min(ans, dis[to] + dis[ver] + 1)
			elif dis[to] == -1:
				dis[to] = dis[ver] + 1
				dq.append(to)
if ans == 10 ** 18:
	print(-1)
else:
	print(ans)


from heapq import heappush, heappop
n = int(input())
sp = list(map(int, input().split()))
gr = [[] for i in range(60)]
for i in range(n):
	j = 0
	while sp[i] != 0:
		if sp[i] % 2 == 1:
			gr[j].append(i)
			if len(gr[j]) == 3:
				print(3)
				exit(0)
		sp[i] //= 2
		j += 1
GR = [[] for i in range(n)]
for i in range(60):
	if len(gr[i]) == 2 and (not gr[i][1] in GR[gr[i][0]]):
		GR[gr[i][0]].append(gr[i][1])
		GR[gr[i][1]].append(gr[i][0])
ans = 1000000000.0
for i in range(60):
	if len(gr[i]) == 2:
		x = gr[i][0]
		y = gr[i][1]
		GR[x].remove(y)
		GR[y].remove(x)
		D = [1000000000.0] * n
		H = [(0, x)]
		while len(H) != 0:
			v = heappop(H)
			if v[0] < D[v[1]]:
				D[v[1]] = v[0]
				for z in GR[v[1]]:
					if D[z] > v[0] + 1:
						heappush(H, (v[0] + 1, z))
		GR[x].append(y)
		GR[y].append(x)
		if D[y] + 1 < ans:
			ans = D[y] + 1
print(ans if ans != 1000000000.0 else -1)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')

def main():
	n = N()
	arr = RLL()
	arr = [i for i in arr if i != 0]
	n = len(arr)
	if n > 130:
		print(3)
	else:
		gp = [[INF] * n for _ in range(n)]
		dit = [[INF] * n for _ in range(n)]
		for i in range(n):
			for j in range(i + 1, n):
				if arr[i] & arr[j]:
					gp[i][j] = 1
					gp[j][i] = 1
					dit[i][j] = 1
					dit[j][i] = 1
		res = INF
		for k in range(n):
			for i in range(k):
				for j in range(i):
					res = min(res, dit[i][j] + gp[i][k] + gp[k][j])
			for l in range(n):
				for r in range(n):
					now = dit[l][k] + dit[k][r]
					dit[l][r] = min(dit[l][r], now)
		print(res if res != INF else -1)
main()


import sys
readline = sys.stdin.readline
from collections import deque
N = int(readline())
A = list(map(int, readline().split()))
A = [a for a in A if a]
limit = 32
table = [0] * limit
for a in A:
	for i in range(limit):
		if a & 1 << i:
			table[i] += 1
if max(table) > 2:
	print(3)
else:
	INF = 10 ** 18 + 3
	N = len(A)
	Edge = [set() for _ in range(N)]
	for i in range(N):
		for j in range(i):
			if A[i] & A[j]:
				Edge[i].add(j)
				Edge[j].add(i)
	ans = INF
	for st in range(N):
		for en in Edge[st].copy():
			Edge[st].remove(en)
			Edge[en].remove(st)
			dist = [INF] * N
			dist[st] = 0
			Q = deque([st])
			while Q:
				vn = Q.pop()
				for vf in Edge[vn]:
					if dist[vf] == INF:
						dist[vf] = 1 + dist[vn]
						Q.appendleft(vf)
			ans = min(ans, 1 + dist[en])
			Edge[st].add(en)
			Edge[en].add(st)
	if ans >= INF:
		ans = -1
	print(ans)


from collections import defaultdict
import queue

class Graph:

	def __init__(self, length):
		self.length = length
		self.graph = defaultdict(list)

	def addEdge(self, u, v):
		self.graph[u].append(v)

	def bfs(self, s, max_len):
		D = [self.length + 1] * self.length
		visited = [False] * self.length
		P = [None] * self.length
		stack = queue.Queue()
		stack.put(s)
		visited[s] = True
		D[s] = 0
		while not stack.empty():
			v = stack.get()
			if D[v] >= max_len:
				break
			for w in self.graph[v]:
				if visited[w] == False:
					visited[w] = True
					stack.put(w)
					D[w] = D[v] + 1
					P[w] = v
				elif P[v] != w:
					return (True, D[v] + D[w] + 1)
		return (False, self.length + 1)
n = int(input())
nums = list(map(int, input().split(' ')))
a = []
for i in range(n):
	if nums[i] != 0:
		a.append(nums[i])
n = len(a)
if n < 3:
	print(-1)
elif n > 120:
	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.addEdge(i, j)
				G.addEdge(j, i)
	min_len = n + 1
	for i in range(n):
		(has_cycle, length) = G.bfs(i, min_len)
		if has_cycle and length < min_len:
			min_len = length
	if min_len == n + 1:
		print(-1)
	else:
		print(min_len)


from collections import deque

def bws(A, si):
	used = [0] * len(A)
	d = [0] * len(A)
	p = [0] * len(A)
	used[si] = True
	p[si] = -1
	q = deque([si])
	while len(q) > 0:
		vert = q.popleft()
		for vi in range(len(A)):
			if vi == vert:
				continue
			if vi == p[vert]:
				continue
			if A[vi] & A[vert] == 0:
				continue
			if used[vi] == False:
				used[vi] = True
				q.append(vi)
				d[vi] = d[vert] + 1
				p[vi] = vert
			else:
				cycle = set()
				k = vert
				while k != si:
					cycle.add(k)
					k = p[k]
				k = vi
				while k != si:
					cycle.add(k)
					k = p[k]
				cycle.add(si)
				return cycle
	return set()

def main():
	n = int(input())
	A = list(map(int, input().split()))
	assert n == len(A)
	A = list(filter(lambda x: x > 0, A))
	n = len(A)
	to_check = set(range(n))
	res = -1
	while len(to_check) > 0:
		si = to_check.pop()
		cycle = bws(A, si)
		r = len(cycle)
		if r != 0:
			res = min(res, r) if res != -1 else r
			if res == 3:
				print(res)
				return
	print(res)
import sys
input = sys.stdin.readline
main()


import os
import sys
from io import BytesIO, IOBase
from collections import deque

def main():
	n = int(input())
	a = []
	for i in map(int, input().split()):
		if i > 0:
			a.append(i)
	if not a:
		print(-1)
		return
	n = len(a)
	b = [0] * 60
	for i in a:
		j = 0
		while i:
			if i & 1:
				b[j] += 1
			j += 1
			i >>= 1
	if max(b) > 2:
		print(3)
	else:
		e = []
		tree = [set() for _ in range(n)]
		for i in range(n):
			for j in range(i + 1, n):
				if a[i] & a[j]:
					e.append((i, j))
					tree[i].add(j)
					tree[j].add(i)
		mi = n + 1
		for (x, y) in e:
			v = [0] * n
			tree[x].discard(y)
			tree[x].discard(y)
			q = deque([(x, 0)])
			v[x] = 1
			ans = n + 1
			while q:
				(z, h) = q.popleft()
				if z == y:
					ans = h + 1
					break
				for i in tree[z]:
					if not v[i]:
						v[i] = 1
						q.append((i, h + 1))
			mi = min(mi, ans)
			tree[x].add(y)
			tree[x].add(y)
		print(-1 if mi == n + 1 else mi)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def naiveSolve(n):
	return
from collections import deque

def main():
	n = int(input())
	a = readIntArr()
	setCnts = [0] * 60
	b = []
	for x in a:
		cnt = 0
		for i in range(60):
			if x & 1 << i > 0:
				cnt += 1
				setCnts[i] += 1
				if setCnts[i] == 3:
					print(3)
					return
		if cnt >= 2:
			b.append(x)
	m = len(b)
	adj = [[] for _ in range(m)]
	for i in range(m):
		for j in range(i + 1, m):
			if b[i] & b[j] > 0:
				adj[i].append(j)
				adj[j].append(i)
	ans = inf
	for i in range(m):
		dist = [-1] * m
		parent = [-1] * m
		q = deque()
		q.append(i)
		dist[i] = 0
		while q:
			node = q.popleft()
			for nex in adj[node]:
				if nex == parent[node]:
					continue
				if dist[nex] == -1:
					dist[nex] = dist[node] + 1
					parent[nex] = node
					q.append(nex)
				else:
					ans = min(ans, dist[node] + dist[nex] + 1)
	if ans == inf:
		print(-1)
	else:
		print(ans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(i, j):
	print('? {} {}'.format(i, j))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(' '.join([str(x) for x in ans])))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
from math import gcd, floor, ceil
for _abc in range(1):
	main()


def int2bin(n):
	bit_cnt = ''
	while n:
		bit_cnt = str(n & 1) + bit_cnt
		n >>= 1
	return bit_cnt.zfill(70)
n = int(input())
if n <= 2:
	print(-1)
	exit(0)
A = list(map(int, input().split()))
B = []
for i in A:
	B.append(int2bin(i))
graph = {i: set() for i in range(n + 55)}
starts = set()
ans = 10 ** 10
for bit in range(69, -1, -1):
	od = []
	for i in range(n):
		if B[i][bit] == '1':
			od.append(i)
			if len(od) >= 3:
				print(3)
				exit(0)
	if len(od) == 2:
		(a, b) = od
		graph[a].add(b)
		graph[b].add(a)
		starts.add(a)
		starts.add(b)
for v in starts:
	used = [0] * (n + 55)
	used[v] = 1
	s1 = {v}
	s2 = set()
	c = 0
	par = {}
	while s1:
		c += 1
		for u in s1:
			for j in graph[u]:
				if used[j] == 0:
					par[j] = u
					s2.add(j)
					used[j] = 1
				elif c > 1 and j != v and (par[u] != j):
					if j in s1:
						ans = min(ans, 2 * c - 1)
					else:
						ans = min(ans, 2 * c)
		s1 = s2
		s2 = set()
if ans == 10 ** 10:
	print(-1)
else:
	print(ans)


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
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)


import sys, os, re, datetime, copy
from collections import *
from bisect import *

def mat(v, *dims):

	def submat(i):
		if i == len(dims) - 1:
			return [copy.copy(v) for _ in range(dims[-1])]
		return [submat(i + 1) for _ in range(dims[i])]
	return submat(0)
__cin__ = None

def cin():
	global __cin__
	if __cin__ is None:
		__cin__ = iter(input().split(' '))
	try:
		return next(__cin__)
	except StopIteration:
		__cin__ = iter(input().split(' '))
		return next(__cin__)

def iarr(n):
	return [int(cin()) for _ in range(n)]

def farr(n):
	return [float(cin()) for _ in range(n)]

def sarr(n):
	return [cin() for _ in range(n)]

def carr(n):
	return input()

def imat(n, m):
	return [iarr(m) for _ in range(n)]

def fmat(n, m):
	return [farr(m) for _ in range(n)]

def smat(n, m):
	return [sarr(m) for _ in range(n)]

def cmat(n, m):
	return [input() for _ in range(n)]
N = 64
n = int(cin())
tmp = iarr(n)
t = mat(0, N)
g = mat([], N)
adj = mat(set(), n)
INF = 100000
ans = INF
a = list(filter(lambda x: x > 0, tmp))
n = len(a)
for j in range(N):
	for i in range(n):
		v = a[i]
		t[j] += v >> j & 1
		if t[j] >= 3:
			print('3')
			exit(0)
		if v >> j & 1 == 1:
			g[j].append(i)
for i in range(N):
	if len(g[i]) == 2:
		adj[g[i][0]].add(g[i][1])
		adj[g[i][1]].add(g[i][0])

def bfs(i):
	dist = mat(INF, n)
	q = deque()
	q.append(i)
	dist[i] = 0
	while len(q) > 0:
		u = q.popleft()
		for v in adj[u]:
			if dist[v] == INF:
				q.append(v)
				dist[v] = dist[u] + 1
			elif dist[v] + 1 != dist[u]:
				return dist[v] + dist[u] + 1
	return INF
for i in range(n):
	ans = min(ans, bfs(i))
print(-1 if ans == INF else ans)


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])
	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 sys import stdin
from sys import setrecursionlimit as SRL
SRL(10 ** 7)
rd = stdin.readline
rrd = lambda : map(int, rd().strip().split())
n = int(rd())
a = list(rrd())
b = []
for i in a:
	if i:
		b.append(i)
a = b[:]
n = len(a)
cnt = [0] * 100
edge = [[] for _i in range(n + 100)]
con = [[] for _j in range(100)]
for (i, v) in enumerate(a):
	for j in range(70):
		if v & 1 << j:
			cnt[j] += 1
			con[j].append(i)
for i in range(70):
	if cnt[i] >= 3:
		print(3)
		exit(0)
for i in range(100):
	for j in con[i]:
		for k in con[i]:
			if k not in edge[j]:
				edge[j].append(k)
			if j not in edge[k]:
				edge[k].append(j)
ans = 1000000

def bfs(s):
	ct = [1000000] * (n + 10)
	q = [[s, 0, 0]]
	ct[s] = 0
	while len(q):
		now = q[0]
		q = q[1:]
		for i in edge[now[0]]:
			if i != now[0] and i != now[2] and (i != s):
				if ct[i] == 1000000:
					ct[i] = now[1] + 1
					q.append([i, ct[i], now[0]])
				else:
					global ans
					ans = min(ans, ct[i] + now[1] + 1)
for i in range(n):
	bfs(i)
if ans == 1000000:
	print(-1)
else:
	print(ans)


from sys import stdin
from collections import deque
INT_MAX = float('inf')

def shortest_cycle(gr):
	ans = INT_MAX
	for i in gr:
		dist = {x: int(1000000000.0) for x in gr}
		par = {x: -1 for x in gr}
		dist[i] = 0
		q = deque()
		q.append(i)
		while q:
			x = q.popleft()
			for child in gr[x]:
				if dist[child] == int(1000000000.0):
					dist[child] = 1 + dist[x]
					par[child] = x
					q.append(child)
				elif par[x] != child and par[child] != x:
					ans = min(ans, dist[x] + dist[child] + 1)
	if ans == INT_MAX:
		return -1
	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))


def bfs(g, src, dest):
	visited = {}
	dist = {}
	for i in g:
		visited[i] = False
		dist[i] = 1e+18
	dist[src] = 0
	visited[src] = True
	q = []
	q.append(src)
	while q:
		src = q.pop(0)
		for i in g[src]:
			if visited[i] == False:
				visited[i] = True
				dist[i] = min(dist[i], dist[src] + 1)
				q.append(i)
	return dist[dest]
n = int(input())
a = list(map(int, input().split()))
c = 0
a = sorted(a)
while n != 0 and a[0] == 0:
	a.pop(0)
	n -= 1
for i in range(64):
	c = 0
	for j in range(n):
		if a[j] >> i & 1:
			c += 1
		if c == 3:
			break
	if c == 3:
		break
if c == 3:
	print(3)
else:
	g = {}
	for i in range(64):
		buff = [-1, -1]
		for j in range(n):
			if a[j] >> i & 1:
				if buff[0] == -1:
					buff[0] = j
				elif buff[1] == -1:
					buff[1] = j
					if buff[0] not in g:
						g[buff[0]] = []
					g[buff[0]].append(buff[1])
					if buff[1] not in g:
						g[buff[1]] = []
					g[buff[1]].append(buff[0])
	tg = {}
	dist = []
	for i in g:
		for j in g[i]:
			tg = g
			tg[i].remove(j)
			tg[j].remove(i)
			dist.append(bfs(tg, i, j))
	while len(dist) != 0 and min(dist) < 2:
		dist.remove(min(dist))
	if len(dist) != 0 and min(dist) < 1e+18:
		print(min(dist) + 1)
	else:
		print(-1)


import math
import sys
DEBUG = False

def inp():
	return sys.stdin.readline().rstrip()

def dprint(*value, sep=' ', end='\n'):
	if DEBUG:
		print(*value, sep=sep, end=end)
INF = 70

def solve(N, A):
	B = [set() for _ in range(63)]
	for (i, a) in enumerate(A):
		if a == 0:
			continue
		m = 1
		for j in range(63):
			if a & m:
				B[j].add((a, i))
				if len(B[j]) == 3:
					return 3
			m <<= 1
	G = {}
	for b in B:
		if len(b) <= 1:
			continue
		((p, _), (q, _)) = list(b)
		if p == q:
			continue
		if p not in G:
			G[p] = set()
		if q not in G:
			G[q] = set()
		G[p].add(q)
		G[q].add(p)
	dprint(G)
	best = INF
	for start in G:
		nodes = set([start])
		level = 1
		visited = set()
		while nodes and level * 2 <= best:
			nnodes = set()
			for i in nodes:
				for j in G[i]:
					if j in nodes:
						best = level * 2 - 1
						break
					if j in nnodes:
						best = min(best, level * 2)
					elif j not in visited:
						nnodes.add(j)
				if best == level * 2 - 1:
					break
			visited |= nodes
			nodes = nnodes
			level += 1
	if best == INF:
		return -1
	return best

def main():
	N = int(inp())
	A = [int(e) for e in inp().split()]
	print(solve(N, A))
main()


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

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
	ans = float('inf')
	for (u, v) in edges:
		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 heapq import *

def bfs(a, b, adj):
	global n, mi
	s = [[0, a]]
	vis = [0] * n
	while s:
		c = heappop(s)
		for i in adj[c[1]]:
			if vis[i]:
				continue
			if i == b:
				mi = min(mi, c[0] + 2)
				return
			else:
				heappush(s, [c[0] + 1, i])
				vis[i] = True
n = int(input())
it = list(map(int, input().split()))
it = [i for i in it if i != 0]
n = len(it)
if len(it) > 124:
	print(3)
else:
	adj = [set() for i in range(n)]
	ss = [list(map(int, list(bin(i)[2:]))) for i in it]
	ma = -1
	ed = []
	for i in range(len(ss) - 1):
		for j in range(i + 1, len(ss)):
			for (k, l) in zip(ss[i][-1::-1], ss[j][-1::-1]):
				if k == 1 and k == l:
					adj[i].add(j)
					adj[j].add(i)
					ed.append([i, j])
					break
	mi = 10 ** 10
	for i in ed:
		adj[i[0]].remove(i[1])
		adj[i[1]].remove(i[0])
		bfs(i[0], i[1], adj)
		adj[i[0]].add(i[1])
		adj[i[1]].add(i[0])
	if mi == 10 ** 10:
		print(-1)
	else:
		print(mi)


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:
				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:
		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)