A sensor network is a simple undirected graph on n sensors numbered 1 through n, joined by cables (no self-cables, and at most one cable between any pair of sensors). A loop is a cycle: a sequence of distinct sensors a1, a2, ..., ak (with k >= 3) such that consecutive sensors are joined by a cable and the last sensor is joined back to the first.

Report the number of cables in the shortest loop (its length). If the network contains no loop at all, report -1.

Input format

Line 1: two integers n and m. Next m lines: two integers u and v, a cable between sensors u and v.

Output format

A single integer: the length of the shortest loop, or -1 if there is none.

Constraints

• 1 <= n <= 300
• 0 <= m <= n * (n - 1) / 2
• The graph is simple (no self-cables, no repeated cable between the same pair).
• 1 <= u, v <= n and u != v

5 6
1 2
2 3
3 1
3 4
4 5
5 3

3

4 4
1 2
2 3
3 4
4 1

4