현대모비스의 주행시험장 트랙을 주행해 볼 수 있는 가상 시뮬레이션 프로그램이 있습니다. 시뮬레이션의 트랙에는 1 ~ n의 서로 다른 번호가 붙은 지점이 n개 있으며, 각 지점마다 고유한 스탬프가 있습니다. 각 지점을 방문할 때 해당 지점의 스탬프를 얻을 수 있습니다. 당신은 1번 지점에서 시작하여 각 지점을 최소 한 번씩 방문해 n가지 스탬프를 모두 모으려 합니다.

지점들은 m개의 단방향 도로로 연결되어 있습니다. 당신은 지점 사이를 이동하기 위해 단방향 도로를 이용할 수 있습니다.

다음은 n = 6인 예시입니다.

• 각 원은 지점을 나타내며, 원 안에 적힌 수는 지점의 번호를 나타냅니다.
• 화살표는 두 지점을 연결하고 있는 단방향 도로를 나타냅니다.

위 예시에서 1번 지점에서 출발해 1 - 2 - 6과 같은 경로로 움직이면 1, 2, 6번 지점의 스탬프 3가지를 모을 수 있습니다. 하지만 6번 지점에 도착하면 더 이상 이용할 수 있는 도로가 없습니다.

시뮬레이션에는 단방향 도로를 이용하는 것 외의 이동 방법으로 빠른 이동 기능이 있습니다. 빠른 이동이란 당신이 스탬프를 얻은 지점 중 원하는 곳으로 순간 이동할 수 있는 기능입니다. 예를 들어 위 예시에서 1 - 2 - 6 - 2(빠른 이동) - 4 - 3 - 5와 같은 경로로 움직이면 모든 지점을 한 번씩 방문해 n가지 스탬프를 모두 모을 수 있습니다.

당신은 n가지 스탬프를 모두 모으기 위해 필요한 빠른 이동의 최소 사용 횟수를 알고 싶습니다.

지점의 수를 나타내는 정수 n과 지점을 연결하는 단방향 도로들의 정보를 담고 있는 2차원 정수 배열 roads가 매개변수로 주어집니다. 이때, 1번 지점에서 출발해 n가지 스탬프를 모두 모으기 위해 필요한 빠른 이동의 최소 사용 횟수를 return 하도록 solution 함수를 완성해 주세요.

제한사항

• 2 ≤ n ≤ 500
• n - 1 ≤ roads의 길이 = m ≤ 100,000
• roads의 원소는 [a, b] 형태입니다.
  • a번 지점에서 b번 지점으로 이동할 수 있는 단방향 도로를 의미합니다.
  • 1 ≤ a, b ≤ n
  • a ≠ b
  • 같은 도로는 최대 한 번만 주어집니다.
• 도착 불가능한 지점이 있는 경우는 주어지지 않습니다.

입출력 예

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

지점들의 연결 상태는 아래 그림과 같습니다.

1 - 2 - 3 - 4 - 5와 같은 경로로 움직이면 빠른 이동을 사용하지 않고 모든 지점을 최소 한 번씩 방문해 5가지 스탬프를 모두 모을 수 있습니다.

따라서 0을 return 합니다.

입출력 예 #3

지점들의 연결 상태는 아래 그림과 같습니다.

1 - 6 - 4 - 5 - 1(빠른 이동) - 2 - 3 - 7 - 1(빠른 이동) - 8과 같은 경로로 움직이면 모든 지점을 최소 한 번씩 방문해 8가지 스탬프를 모두 모을 수 있으며, 이보다 빠른 이동을 적게 사용하는 방법은 없습니다.

따라서 2를 return 합니다.

입출력 예 #4

지점들의 연결 상태는 아래 그림과 같습니다.

1 - 2 - 5 - 6 - 9 - 1(빠른 이동) - 4 - 5 - 7 - 5(빠른 이동) - 8 - 1(빠른 이동) - 3과 같은 경로로 움직이면 모든 지점을 최소 한 번씩 방문해 9가지 스탬프를 모두 모을 수 있으며, 이보다 빠른 이동을 적게 사용하는 방법은 없습니다.

따라서 3을 return 합니다.

입출력 예 #5

지점들의 연결 상태는 아래 그림과 같습니다.

1 - 2 - 3 - 6 - 1(빠른 이동) - 7 - 4 - 5와 같은 경로로 움직이면 모든 지점을 최소 한 번씩 방문해 7가지 스탬프를 모두 모을 수 있으며, 이보다 빠른 이동을 적게 사용하는 방법은 없습니다.

따라서 1을 return 합니다.