선거가 가까워지고 있어서, 대통령은 WDC와 LA에 연설하기 위해 도시 순회를 계획하고 있다. 충분한 보안을 제공하기 위해, 경호 기관에서는 대통령이 통과할 모든 도시(WDC와 LA를 포함하여)를 계속 주시하는 것을 요구한다.

물론, 연방 예산을 책임감 있게 사용해야하므로, 대통령은 AF1을 사용하지 못하지만 자동차로 다닐 수는 있다. 또한, 경호 기관에서는 WDC부터 LA까지, 그리고 WDC로 주시할 필요가 있는 도시가 최소가 되도록 대통령 투어를 계획할 예정이다.

이 문제를 위해, 도시들은 1부터 N까지 번호가 정해져있고, M개의 서로 다른 도시 사이의 단일 방향 고속도로가 연결되어있다. WDC는 1번, LA는 2번이다. 주시해야할 도시의 최소 수를 구하여라.

예를 들어보자. 각 도시의 연결이 다음과 같이 되어있다면,

다음과 같은 경로로 WDC에서 LA를 가고, LA에서 다시 WDC로 돌아오면 된다. 초록선은 WDC에서 LA를 가는 경로이고, 빨간선은 LA에서 돌아오는 경로이다.

입력

• 첫번째 줄이는 정수 N과 M이 주어진다. (2 ≤ N ≤ 100, 2 ≤ M ≤ 200)
• M개의 각각의 줄에는 시작과 끝 도시의 정보인 서로 다른 두 수 A, B가 주어진다. (1 ≤ A, B ≤ N) 같은 두 도시의 같은 방향을 지닌 두 고속도로는 없지만, 같은 두 도시의 서로 다른 방향을 지닌 두 고속도로는 있을 수 있다.

출력

입출력 예

입력

6 7
1 3
3 4
4 5
5 1
4 2
2 6
6 3

출력

6

입력

9 11
1 3
3 4
4 2
2 5
5 3
3 6
6 1
2 7
7 8
8 9
9 1

출력

6

출처:coci 2012
번역:Fate