Minimum Cycle in Exponentially Weighted Graph

BaoBao just learned how to use a data structure called link-cut tree to find cycles in a graph. She is given an undirected graph with n vertices and m edges, where the length of the i-th edge equals \(2^i\). She needs to find a simple cycle (a cycle that contains at least 3 vertices) whose total length is minimized.

A simple cycle is defined as a sequence of distinct vertices \(a_1, a_2, \ldots, a_k\) (with \(k \ge 3\)) and k edges such that for each \(1 \le i \le k\), there is an edge connecting \(a_i\) and \(a_{(i \bmod k) + 1}\). The length of a cycle is the sum of the lengths of its edges. In this problem, the length of the i-th edge is \(2^i\>.

If no simple cycle exists, output -1.

inputFormat

The first line contains two integers \(n\) and \(m\), representing the number of vertices and edges respectively.

Each of the next \(m\) lines contains two integers \(u\) and \(v\), indicating an undirected edge between vertices \(u\) and \(v\). The edges are given in order from 1 to \(m\), and the weight of the i-th edge is \(2^i\).

outputFormat

If there exists a simple cycle (with at least 3 vertices), output the total length of the cycle. Otherwise, output -1.

sample

4 4
1 2
2 3
3 4
4 1

30