解题思路

• 将每个数看作一个点，若 ai & aj != 0 则两点间连一条无向边，求图的最短环长度（环的最小长度为 3）。

• 关键剪枝：若某一位的置位数量 ≥ 3，则这三个点两两都有该位相连，答案必为 3。又因为最高只需考虑 0~60 位（ai ≤ 1e18），若非零数的个数 m > 120，按抽屉原理必有某位出现 ≥3 次，直接输出 3。

• 否则每一位最多出现 2 次，非零点数 m ≤ 120。此时可以把这些点显式建图：

  • 对所有两两点判断一次按位与是否为正，若是则加边。
  • 用 BFS 从每个起点求最短环：BFS 过程中若遇到已访问且不是父亲的点 v，就发现了一个环，长度更新为 dist[u] + dist[v] + 1。

• 若最终没有发现环，输出 -1。

题目内容

考虑一个有 $n$ 个节点的图，每个节点对应一个整数，其有 $n$ 个整数

$a_1,a_2,a_3,…,a_n$ ，当且仅当 $a_i$ & $a_j≠0$ 时表示节点 $i$ 和节点 $j(i≠j)$ 之间有一条边，其中 & 表示按位与操作。

例如:

$3$ & $6:3$ 的二进制表示是 $0 1 1$ ，$6$ 的二进制表示是 $110$，$3$ ＆ $6=2$ (二进制 $010$ )不为 $0$ ，表示 $3$ 和 $6$ 之间有一条边。

$3$ & $28:3$ 的二进制表示是 $00011$，$28$ 的二进制表示是 $11100$ ，$3$ ＆ $28=0$ ，表示 $3$ 和 $28$ 之间没有边。

请找出该图中最短的环的长度(环的最小长度是 $3$ )，如果图中没有环输出 $-1$ 。

输入描述

第一行输入一个整数 $n(1≤n≤10^6)$ ，表示数字的个数。

第二行输入 $n$ 个整数 $a_1,a_2,…,a_n(0≤a_i≤10^{18})$，表示数字序列。(输入的数字有可能重复)

输出描述

如果图中没有环，输出 $-1$ 。

否则输出最短环的长度。

样例1

输入

10
448 0 112 0 0 0 28 260 3 0

输出

4

说明

$448$ $112$ $28$ $260$ $3$ 的二进制表示为:

$448:111000000$

$112:001110000$

$28:000011100$

$260:100000100$

$3:000000011$

$448$ $-112$ $-28$ $-260$ 构成环，长度为 $4$ 。

样例2

输入

1
1000000000000000000

输出

-1

说明

一个节点无法构成环

样例3

输入

4
1 2 4 8

输出

-1

说明

$1$ $2$ $4$ $8$ 的二进制表示为:

$1:0001$

$2:0010$

$4:0100$

$8:1000$

节点之间两两没有连接，无法构成环。

样例4

输入

4
3 6 28 5

输出

3

说明

$3$ $6$ $28$ $5$ 的二进制表示为:

$3:00011$

$6:00110$

$28:11100$

$5:00101$

$3$ 和 $6$ 相连，$6$ 和 $28$ 相连，$5$ 和 $3$ 相连，$3-6-5$ 构成了一个环，长度为 $3$

样例5

输入

4
3 6 28 9

输出

4

说明

$3$ $6$ $28$ $9$ 的二进制表示为:

$3:00011$

$6:00110$

$28:11100$

$9:01001$

$3$ 和 $6$ 相连，$6$ 和 $28$ 相连，$28$ 和 $9$ 相连，$9$ 和 $3$ 相连，$3-6-28-9$ 构成了一个环，长度为 $4$