Masala #1074

Xotira 16 MB Vaqt 1000 ms
14

Velosiped poygasi

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.


Kiruvchi ma'lumotlar:

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.


Chiquvchi ma'lumotlar:

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


Misollar
# input.txt output.txt
1
8 14
6 7
6 8
7 5
5 2
5 3
4 8
1 6
5 2
7 5
6 4
1 4
5 2
7 4
8 3
6