Masala #1074

Bitlandiyada n ta shahar mavjud bo'lib 1 dan n gacha raqamlangan. Velosiped poygasi esa 1-shaharda boshlanib 2-shahrda tugaydi. Shuningdek ushbu shaharlarni bog'lovchi M ta bir tomonlama yo'llar mavjud. 1-shahardan 2-shaharga borishni necha xil yo'li borligini aniqlovchi dastur tuzing. Agar javob cheksiz bo'lsa inf, juda katta bo'lsa oxirigi 9 ta raqamini chop eting.

Kirish faylining 1-qatorida N va M natural sonlari kiritialadi.(1 ≤ N ≤ 10 000, 1 ≤ M ≤ 100 000)

Keyingi M ta qatorda 2 ta turli sonlar A, va B kiritiladi. A shahardan B shaharga yo'l borligini bildiradi.

Ikkita shahar orasida bir qancha yo'llar bo'lishi mumkin.

Chiqish faylida masala javobini chop eting.Agar javob cheksiz bo'lsa inf, juda katta bo'lsa oxirgi 9 xonani chop eting.