대피

테러 위협이 점점 커지자, 바이트랜드 방위국(ADB)은 공격에 대비한 대응 계획을 마련하기로 했다. 방위국의 가장 중요한 관심사는 폭격이 일어났을 때 바이트랜드의 왕을 신속하게 대피시킬 수 있도록 하는 것이다.

왕궁은 바이트랜드 수도의 어느 한 교차로 옆에 있고, 대피소는 또 다른 교차로 옆에 있다. 위험이 닥치면 왕은 즉시 대피소로 옮겨져야 한다. 방위국은 수도의 정확한 도로망 지도를 가지고 있는데, 이 지도는 교차로들과 그것들을 잇는 일방통행 거리들로 이루어져 있다.

대피 경로가 거리를 최대 세 개까지만 지난다면 그 경로를 신속한 경로라고 한다. 어떤 거리에 폭격이 가해지면 그 거리는 왕의 행렬이 지날 수 없게 된다. 방위국은 왕에게 신속한 대피 경로가 하나도 남지 않도록 하려면 최소 몇 개의 거리를 폭격해야 하는지 알고 싶어 한다.

첫째 줄에 두 정수 $n$과 $m$이 주어진다 ($2 \le n \le 1000$, $0 \le m \le n(n-1)$). 각각 수도의 교차로 수와 거리 수를 나타낸다. 교차로는 $1$번부터 $n$번까지 번호가 매겨져 있으며, 왕궁은 $1$번 교차로 옆에, 대피소는 $n$번 교차로 옆에 있다.

이어지는 $m$개의 줄에는 각각 두 정수 $a_i$와 $b_i$가 주어진다 ($1 \le a_i, b_i \le n$, $a_i \ne b_i$). 이는 교차로 $a_i$에서 교차로 $b_i$로 향하는 일방통행 거리를 뜻한다. 교차로의 순서쌍 각각에 대해, 앞 교차로에서 뒤 교차로로 가는 거리는 최대 하나만 존재한다.

왕에게 거리를 최대 세 개까지 지나는 대피 경로가 하나도 남지 않도록 하기 위해 폭격해야 하는 거리의 최소 개수를 정수 하나로 출력한다.

위 그림에서는 거리 $1 \to 3$과 $3 \to 5$를 폭격하면(그림에서 가위표로 지워진 부분) 신속한 대피 경로가 하나도 남지 않는다.