Một ngày nọ Bình đi xe đạp từ phía bắc nha trang qua phía nam nha trang. Trong thành phố có các đường và đi qua các điểm giao nhau. Các điểm giao nhau được đánh số từ 1 * đến *N, và có M cạnh. Cạnh thứ i được nối từ ~a_i~ đến ~b_i~

        Funttion DFS(v): 
            mark v as visited 
            for each neighbor u of v: 
                if u is not visited: 
                    DFS(u)

Yêu cầu:

Hãy giúp Bình xác định xem có tồi tại chu trình có chứa đỉnh 1 hay không, nếu có tìm số cạnh nhất của chu trình đó.

Đầu vào:

từ thiết bị chuẩn gồm

• Dòng thứ nhất chứa 2 số nguyên N và M. (2 ≤ N ≤ 2 x ~10^5~ ; 1 ≤ M ≤ min(N(N-1)/2, 2 x ~10^5~)
• N dòng tiếp theo chứa 2 số nguyên ~a_i~ và ~b_i~ (1 ≤ ~a_i~, ~b_i~ ≤ N)

Đầu ra:

Nếu tồn tại một chu trình chứa đỉnh 1 thì in thiết bị chuẩn số cạnh tối thiểu trong số các chu kỳ đó. Ngược lại, in -1

Ví dụ:

Input 1

3 3
1 2
2 3
3 1

Output 1

3

Input 2

3 2
1 2
2 3

Output 2

-1