농부 존의 N(1 <= N <= 1,000)마리의 소들은 각각 다른 양의 비율로 우유를 생산한다. 그리고 존은 소들을 우유 생산량에 따라 생상량이 가장 높은 소부터 가장 느린 까지 정렬하고 싶어 한다.

존은 이미 M(1 <= M <= 10,000)쌍의 소에 대한 우유 생산량의 비율을 비교했다. 존은 이와같은 C개의 추가적인 소의 쌍 리스트를 만들기 원한다. 만약 존이 이 C개의 쌍을 비교한다면 N마리의 모든 소의 순서를 확실히 추론 하는게 가능하다.

존을 도와 소의 순서를 결정지을 수 있게 하는 C의 최소값을 알아내자.

입력

* 첫줄 : 공백으로 구분되는 두개의 정수 : N과 M
* 두번째줄 .. M+1줄 : 공백으로 구분되는 두개의 정수, X와 Y. X와 Y은 1부터 N까지 이며 X가 Y보다 더 높다는 것을 의미한다.

출력

입출력 예

입력

5 5
2 1
1 5
2 3
1 4
3 4

출력

3

입출력 보충

출력값:
5개의 비교값으로 농부 존은 2번째 소 > 1번째 소 > 5번째 소 의 순서와 2번째 소 > 3번째 소 > 4번째 소 의 순서를 알 수 있으므로, 2번째 소가 가장 상산률이 높은 소이다.
하지만 존은 2번째로 생산률이 높은 소가 누군지 알기 위해 1번째 소가 3번째 소보다 높은 우유 생산률을 가지고 있는지 알아야 할 필요가 있다. 마찬가지로, 존은 4번째 소와 5번째 소 사이의 순서를 결정하기 위한 정보도 필요하다. 그 후 존은 1번째 소가 3번째 소보다 생산률이 높다면 5번째 소가 3번째 소보다 생산률이 높은지 알아야 한다. 결국 존은 소들의 순서를 확실히 하기 위해서는 3개의 순서 쌍이 더 필요하다. "1번째 소가 3번째 소보다 낫나? 4번째 소가 5번째 소보다 낫나? 5번째 소가 3번째 소보다 낫나?"

출처:usaco 2007 March GOLD
번역:makecode