306488: CF1205B. Shortest Cycle
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Shortest Cycle
题意翻译
给定 $n$ 个整数 $a_1,\,a_2,\,\cdots,a_n$ ,考虑一张含有 $n$ 个节点的图,对于任意 $i\ne j$ ,若 $a_i\;\text{and}\;a_j\ne 0$ ,则节点 $i,\,j$ 连通,其中 $\text{and}$ 表示按位与运算 你现在需要求出该图最小环的大小,或确定其不存在环 输入格式 第一行一个整数 $n\le 10^5$ 第二行包含 $n$ 个整数,第 $i$ 个数表示 $a_i$ ($\le a_i\le 10^{18}$) 输出格式 仅一个数,表示最小环的大小,若不存在环,则输出 $-1$题目描述
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](https://en.wikipedia.org/wiki/Bitwise_operation#AND). Find the length of the shortest cycle in this graph or determine that it doesn't have cycles at all.输入输出格式
输入格式
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} $ ).
输出格式
If the graph doesn't have any cycles, output $ -1 $ . Else output the length of the shortest cycle.
输入输出样例
输入样例 #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