끝나지 않는 BFS

엔도 씨는 무방향 그래프의 모든 정점을 탐색하는 알고리즘인 너비 우선 탐색(BFS)을 구현하려고 했다. BFS의 의사 코드 예시는 다음과 같다.

1: $current \leftarrow \{start\_vertex\}$
2: $visited \leftarrow current$
3: while $visited \ne$ the set of all the vertices
4:   $found \leftarrow \{\}$
5:   for $v$ in $current$
6:     for each $u$ adjacent to $v$
7:       $found \leftarrow found \cup \{u\}$
8:   $current \leftarrow found \setminus visited$
9:   $visited \leftarrow visited \cup found$

그런데 엔도 씨는 코드에서 방문한 정점을 관리하는 부분을 빠뜨린 모양이다. 그가 실제로 작성한 코드는 다음과 같다.

1: $current \leftarrow \{start\_vertex\}$
2: while $current \ne$ the set of all the vertices
3:   $found \leftarrow \{\}$
4:   for $v$ in $current$
5:     for each $u$ adjacent to $v$
6:       $found \leftarrow found \cup \{u\}$
7:   $current \leftarrow found$

어떤 그래프에서는 엔도 씨의 프로그램이 무한히 실행되어 멈추지 않는다는 것을 알 수 있다. 하지만 그렇다고 해서 모든 정점을 유한한 단계 안에 탐색할 수 없는 것은 아니다. 자세한 내용은 아래 예제 2를 참고하라. 여러분의 과제는 엔도 씨에게 버그를 알려주기 위해, 주어진 그래프에 대해 엔도 씨의 프로그램이 유한한 단계 안에 멈추는지 판별하는 프로그램을 작성하는 것이다. 또한 멈춘다면 프로그램이 멈추기 위해 필요한 최소 반복 횟수도 계산하라.

입력은 다음과 같은 형식의 단일 테스트 케이스로 주어진다.

$N$ $M$
$U_{1}$ $V_{1}$
$\vdots$
$U_{M}$ $V_{M}$

첫째 줄에는 두 정수 $N$ ($2 \le N \le 100{,}000$)과 $M$ ($1 \le M \le 100{,}000$)이 주어진다. $N$은 정점의 수, $M$은 주어진 무방향 그래프의 간선 수이다. 이어지는 $M$개의 줄 중 $i$번째 줄에는 두 정수 $U\_{i}$와 $V\_{i}$ ($1 \le U\_{i}, V\_{i} \le N$)가 주어지며, 이는 정점 $U\_{i}$와 $V\_{i}$가 인접함을 뜻한다. 정점 1이 시작 정점, 즉 의사 코드의 $start\_vertex$이다. 주어진 그래프는 다음 조건도 만족한다.

• 자기 간선이 없다. 즉, 모든 $1 \le i \le M$에 대해 $U\_{i} \ne V\_{i}$이다.
• 중복 간선이 없다. 즉, 모든 $1 \le i < j \le M$에 대해 $\{U\_{i}, V\_{i}\} \ne \{U\_{j}, V\_{j}\}$이다.
• 연결 그래프이다. 즉, 모든 정점 $1 \le U, V \le N$에 대해 $U$에서 $V$로 가는 경로가 적어도 하나 존재한다(반대 방향도 마찬가지이다).

주어진 입력 그래프에 대해 엔도 씨의 잘못된 BFS 코드가 유한한 단계 안에 멈추지 않는다면 -1을 한 줄에 출력한다. 그렇지 않다면 멈추기 위해 필요한 최소 반복 횟수를 출력한다.