17227번 - 그래서 팩 주냐? 서브태스크

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

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

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

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

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

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

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

두 번째 줄부터 E개의 줄에 걸쳐 간선의 정보를 나타내는 두 정수 u, v(1 ≤ u, v ≤ N)가 주어진다. 이는 u에서 나가 v로 들어오는 간선이 패턴에 존재한다는 의미이다. 동일한 간선이 중복되는 경우는 없다.

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

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

• 시작 화제와 N번 화제를 제외한 모든 화제는 들어오는 간선과 나가는 간선의 수가 1이다.
• 2 ≤ N ≤ 1,000
• N-1 ≤ E ≤ 2×N-3

• 지문에서 설명된 것 외에 각 화제의 간선 제한은 없다.
• 2 ≤ N ≤ 100,000
• N-1 ≤ E ≤ min(N×(N-1)/2, 300,000)

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

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