← 返回题目列表

Codeforces · 1205/B

B. 最短周期

中文机器翻译题面 查看原题

给你 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$。考虑 $$$n$$$ 节点上的图,其中节点 $$$i$$$、$$$j$$$ ($$$i\neq j$$$) 连接当且仅当 $$$a_i$$$ AND $$$a_j\neq 0$$$,其中 AND 表示按位 AND 运算。

找出该图中最短循环的长度或确定它根本没有循环。

输入

第一行包含一个整数 $$$n$$$ $$$(1 \le n \le 10^5)$$$ — 数字的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^{18}$$$)。

输出

如果图形没有任何循环,则输出$$$-1$$$。否则输出最短周期的长度。

示例

输入 #1

4
3 6 28 9

输出 #1

4

输入 #2

5
5 12 9 16 48

输出 #2

3

输入 #3

4
1 2 4 8

输出 #3

-1

注意

在第一个示例中,最短周期是 $$$(9, 3, 6, 28)$$$。

在第二个示例中,最短周期是 $$$(5, 12, 9)$$$。

第三个示例中的图表没有循环。