학원에 학생 N명이 있고, 서로 아는 사이가 M쌍 있어요. 1번 학생의 소식이 친구를 건너서 N번 학생에게 전해지려면 최소 몇 명을 거쳐야 할까요? 소식은 한 단계에 아는 사이끼리만 전해져요.
입력
첫째 줄에 학생 수 N과 아는 사이 수 M이 주어져요. (2 ≤ N ≤ 1,000, 1 ≤ M ≤ 5,000) 다음 M개의 줄에 서로 아는 두 학생의 번호가 주어져요.
출력
소식이 전해지는 최소 단계 수를 출력해요. 1번의 친구는 1단계예요. 전해질 수 없으면 -1을 출력해요.