소들의 순위 매기기

농부 John에게는 소가 $N$마리 있고 ($1 \le N \le 1000$), 각 소는 서로 다른 양의 속도로 우유를 생산한다. John은 우유를 가장 빨리 생산하는 소부터 가장 느린 소까지 순서대로 정렬하려고 한다.

John은 이미 소 쌍 $M$개 ($1 \le M \le 10000$)의 우유 생산 속도를 비교해 두었다. 이제 그는 소 쌍 $C$개를 추가로 골라, 그 $C$개의 쌍까지 비교하고 나면 $N$마리 소 전체의 정확한 순서를 확실히 알아낼 수 있도록 목록을 만들고 싶다. 이러한 목록이 가능하도록 하는 $C$의 최솟값을 구하여라.

• 첫째 줄: 공백으로 구분된 두 정수 $N$과 $M$.
• 둘째 줄부터 $M+1$번째 줄까지: 공백으로 구분된 두 정수 $X$와 $Y$ ($1 \le X, Y \le N$). 이는 소 $X$가 소 $Y$보다 순위가 높다(우유를 더 빨리 생산한다)는, 이미 알려진 비교 결과를 나타낸다.

• 첫째 줄: $C$의 최솟값인 정수 하나.

John이 소 5마리를 비교하며, 이미 소 2 > 소 1, 소 1 > 소 5, 소 2 > 소 3, 소 1 > 소 4, 소 3 > 소 4임을 알아냈다고 하자 (여기서 '>'는 "우유를 더 빨리 생산한다"는 뜻이다).

이 5개의 결과로부터 John은 소 2 > 소 1 > 소 5이고 소 2 > 소 3 > 소 4이므로 소 2의 순위가 가장 높다는 것을 안다. 하지만 두 번째로 높은 소를 정하려면 소 1과 소 3을 비교해야 하고, 소 4와 소 5의 순서를 정하려면 한 번 더 비교해야 하며, 만약 소 1이 소 3보다 높다면 소 5와 소 3도 비교해야 한다. 따라서 전체 순위를 확신하려면 세 번의 질문을 해야 한다: "소 1 > 소 3인가? 소 4 > 소 5인가? 소 5 > 소 3인가?"