Cho trước một đồ thị vô hướng, bạn cần phải xác định chu vi của nó, tức là độ dài của chu trình ngắn nhất có trong đồ thị.

Input

• Dòng đầu chứa hai số nguyên \(n,m\) là số lượng đỉnh và cạnh. Các đỉnh được đánh số \(1,2,\dots,n\)
• Sau đó là \(m\) dòng mô tả các cạnh. Mỗi dòng chứa hai số nguyên \(a\) và \(b\): có một cạnh nối giữa hai đỉnh \(a\) và \(b\)
• Dữ liệu đảm bảo đồ thị đã cho là đơn đồ thị (tối đa một cạnh nối giữa mỗi cặp đỉnh)
• Giới hạn:
  • \(1 \leq n \leq 2500\)
  • \(1 \leq m \leq 5000\)

Output

• Một số nguyên duy nhất là chu vi của đồ thị. Nếu không có chu trình, in ra \(-1\)

Example

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

3