문제 설명

고양이 마을에 '냥냥 노선'이라는 미니 전철망이 생겼어요. 역들은 통로로 직접 연결되어 있고, 연결된 두 역 사이는 한 번에 이동할 수 있습니다. 모든 통로의 길이는 똑같다고 생각해도 됩니다(가중치 없음). 출발역에서 목적역까지 가려면 통로를 최소 몇 번 타야 할까요? 통로 한 번 타는 것을 '이동 1회'로 셉니다.

입력

출력

제약 조건

• •1 ≤ N ≤ 1000
• •통로는 양방향이며 가중치(거리)는 모두 동일
• •같은 두 역 사이에 통로가 중복으로 주어질 수 있음

예제

7 7
0 1
0 2
1 3
3 4
2 5
5 4
2 6
0 4

3