SPOJ in Armenian

N քաղաքների միացված են M միակողմանի ճանապարհներով։ Քաղաքները համարակալված են 1-ից N թվերով։ Հարկավոր է կազմակերպել ավտոմրցույթի համար երթուղի, որը սկսվի 1 համարի քաղաքում և ավարտվի 2 համարի քաղաքում։ Հարկավոր է պարզել, թե քանի տարբեր եղանակով է կարելի դա անել։ Երկու երթուղի կհամարենք տարբեր, եթե նրանք ճիշտ նույն ճանապարհներից չեն կազմված։

Մուտքը

Առաջին տողում տրված են N (1 <= N <= 10000) և M (1 <= M <= 100 000) ամբողջ թվերը։ Հաջորդ M տողերից յուրաքանչյուրը պարունակում է երկու A և B թվեր. Նշանակում է A քաղաքից B քաղաք տանող ճանապարհ կա։ Երկու քաղաք կարող են միացված լինել մի քանի ճանապարհներով։

Ելքը

Ելքում պետք է արտածել մի թիվ՝ պահանջվող քանակը։ Եթե այդ թիվը մեծ է, բավական է արտածել վերջին 9 նիշերը։ Եթե հնարավոր են անվերջ թվով երթուղիներ, արտածել inf բառը։

Օրինակ

Մոուտքը.
6 7
1 3
1 4
3 2
4 2
5 6
6 5
3 4

Ելքը.
3
 
Մոուտքը.
6 8
1 3
1 4
3 2
4 2
5 6
6 5
3 4
4 3

Ելքը.
inf