시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 64 MB 0 0 0 0.000%

문제

Mirko radi najbolju tortu u selu. To je naravno, torta od sira s grejpom. Kako bi reklamirao svoj recept, odlučio je donirati barem po jednu tortu svakom od N sela u svojoj županiji. U tu svrhu će unajmiti odreñen broj trgovačkih putnika koji mogu nositi proizvoljno mnogo torti i dijeliti ih krećući se po jednosmjernim cestama koje povezuju sela.

Koliko najmanje trgovaca mora Mirko unajmiti tako da sva sela dobiju svoju tortu? Svi trgovci kreću iz Mirkovog sela, a ono je označeno brojem 1. Mirko odreñuje putanje svim trgovcima koje unajmi. 

입력

U prvom retku ulaza nalaze se prirodni brojevi N i E takvi da je N ≤ 500, E ≤ 50 000, broj sela i broj cesta.

U svakom od sljedećih E redaka nalaze se po 2 prirodna broja A i B (A, B ≤ N) koji označavaju da postoji jednosmjerna cesta koja povezuje selo označeno brojem A i selo označeno brojem B, odnosno da trgovac može izravno iz sela A preći u selo B. 

출력

U prvi i jedini redak izlaza potrebno je ispisati minimalni broj trgovaca koje Mirko treba unajmiti. Ulazni podaci će biti takvi da će rješenje uvijek postojati. 

예제 입력 1

3 4
1 2
1 2
2 3
2 3

예제 출력 1

1

예제 입력 2

4 4
1 2
1 3
2 4
3 4

예제 출력 2

2

예제 입력 3

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

예제 출력 3

1