시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 16 8 7 100.000%

문제

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

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

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

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

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

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

입력

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

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

출력

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

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

서브태스크 1 (100점)

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

서브태스크 2 (40점)

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

예제 입력 1

4 3
1 4
3 1
2 4

예제 출력 1

0

준표가 3번 화제를 시작 화제로 말을 걸면 만영이가 두 번째 화제로 고를 수 있는 것은 1번 화제밖에 없다. 이후 준표는 세 번째 화제로 4번 화제를 고를 수 있다.

예제 입력 2

6 8
1 2
1 3
1 4
2 5
5 6
3 6
4 6
1 6

예제 출력 2

2

준표는 1번 화제를 시작 화제로 만영이에게 말을 건다. 이때 만영이는 두 번째 화제로 자신이 6번 화제를 고르거나, 이후 6번 화제를 고를 수 있는 2번 화제를 고르려고 할 것이다. 준표는 2번의 정색으로 만영이가 두 번째 화제로 2, 6번 화제를 고르는 것을 막을 수 있다. 이제 만영이가 두 번째 화제로 무엇을 골라도 준표는 세 번째 화제로 6번 화제를 고를 수 있다.

예제 입력 3

8 12
1 2
1 3
1 4
1 6
2 5
3 5
4 5
5 8
6 8
1 7
7 8
5 6

예제 출력 3

1

예제 입력 4

8 12
3 2
2 6
6 7
7 8
6 8
3 4
4 2
4 8
3 5
5 7
1 5
1 8

예제 출력 4

2

힌트

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

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

채점

  • 예제는 채점하지 않는다.