Codah ClubVježbaj. Pošalji. Napreduj.
Prijavi se
Hrvatski
#0002F3

Bickli

U jednoj dalekoj zemlji održava se biciklistička utrka. Zemlja ima N gradova označenih brojevima od 1 do N i M jednosmjernih cesta. Grad s brojem 1 označen je kao start, a grad s brojem 2 kao cilj. Na koliko različitih načina možemo postaviti stazu za utrku? Dvije staze su različite ako ne idu istim cestama.


InputU prvom redu nalaze se dva prirodna broja N i M (1 ≤ N ≤ 10 000, 1 ≤ M ≤ 100 000) – broj gradova i broj cesta. U sljedećih M redaka nalaze se po dva različita broja A i B. To znači da postoji jednosmjerna cesta koja vodi iz grada A u grad B. Moguće je da postoji više istosmjernih cesta koje povezuju iste parove gradova.

OutputU prvi i jedini red ispišite ukupan broj različitih staza. Ako taj broj ima više od 9 znamenaka ispišite samo zadnjih 9 znamenaka tog broja. Ako postoji beskonačno mnogo različitih staza, tada ispišite "inf".

Ulaz
6 7
1 3
1 4
3 2
4 2
5 6
6 5
3 4
Izlaz
3


Ulaz
6 8
1 3
1 4
3 2
4 2
5 6
6 5
3 4
4 3
Izlaz
inf


Ulaz
31 60
1 3
1 3
3 4
3 4
4 5
4 5
5 6
5 6
6 7
6 7
…
…
…
28 29
28 29
29 30
29 30
30 31
30 31
31 2
31 2
Izlaz
073741824

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.