그래서 팩 주냐?

'돌게임'의 일부 유저들은 '그팩주 화법'을 구사한다. '그팩주 화법'이란 상대와 대화하는 중에 화제가 카드팩과 아무 관련이 없어도 "그래서 팩 주냐?"라고 말하며 대화를 끝내버리는 화법이다. 물론 아무 맥락에서나 쓸 수는 없고, 몇몇 대화의 흐름에서만 쓸 수 있다. 또한 대화를 강제로 끝내는 것이므로 당하는 사람은 기분이 나쁠 수 있다.

준표와 만영이의 대화는 항상 '그팩주'로 끝나는 일정한 패턴으로 이루어진다. 이 패턴은 $N$개의 화제로 이루어져 있으며, 각 화제에서 다른 화제로 넘어가는 방향 그래프로 표현된다. 예를 들어 정점 $u$에서 나가 정점 $v$로 들어오는 간선이 존재한다는 것은 $u$번 화제 다음에 $v$번 화제를 고를 수 있다는 뜻이다. 골랐던 화제를 이후 다시 고를 수 있는 사이클은 존재하지 않는다.

<그림1> 패턴 그래프의 한 예(예제4)

두 사람은 번갈아 화제를 고른다. 준표가 먼저 대화를 시작했다면 이를 포함한 홀수번째 화제는 준표가, 짝수번째 화제는 만영이가 고른다. 이 중 $N$번 화제가 바로 '그팩주'이므로, $N$번 화제를 고른 사람이 "그래서 팩 주냐?"로 대화를 끝내버린다. 모든 대화의 흐름이 $N$번 화제로 수렴한다는 것을 기억하자.

준표의 목표는 자신이 먼저 '그팩주' 화제를 고르는 것이다. 이를 위해 준표는 만영이가 화제를 고를 때마다 정색을 하고, 이번 차례에는 그 화제를 고르지 못하도록 할 수 있다. 즉 정색 한 번으로 간선을 하나씩 제한할 수 있으며, 같은 차례에 이를 반복할 수 있다. 준표가 고통받는 것을 즐기는 만영이는 준표가 최대한 많이 정색하게 만드는 방향으로 화제를 고를 것이다. 물론 그 과정에서 '그팩주' 화제를 자신이 먼저 선점한다면 더할 나위 없다.

'시작 화제'란 들어오는 간선이 0개인 화제를 말한다. 준표는 이 중 하나를 골라 대화를 시작하려고 한다. 이때 준표가 "그래서 팩 주냐?"로 대화를 끝내기 위해 필요한 최소 정색 횟수를 구해 보자.

첫 줄에는 화제의 개수 $N$과 패턴을 이루는 간선의 수 $E$가 주어진다.

두 번째 줄부터 $E$개의 줄에 걸쳐 간선의 정보를 나타내는 두 정수 $u$, $v$ ($1 \le u, v \le N$)가 주어진다. 이는 $u$에서 나가 $v$로 들어오는 간선이 패턴에 존재한다는 뜻이다. 같은 간선이 두 번 주어지는 경우는 없다.

한 줄에 준표가 "그래서 팩 주냐?"를 먼저 외치기 위해 필요한 최소 정색 횟수를 출력한다.

어떻게 해도 준표가 "그래서 팩 주냐?"로 대화를 끝내는 것이 불가능하다면 -1을 출력한다.

예제3, 예제4는 서브태스크1에서 나오지 않는다.

<그림2> 서브태스크1에서 나올 수 있는 패턴 그래프의 형태