eolymp
Yarışlar

KBTU OPEN 2014 Spring

Qrafın parçalanması

Bir dəfə Camal şəbəkədə marşurutlaşdırma məsələsini həll edirdi. O təsbit etdi ki, onun qrafı istiqamətlənmişdir və dövrü deyildir. Sərvər gəlib məsələyə baxdığı zaman o çox təcübləndi ki, Camalın qrafını tillərə görə kəsişməyən yollar dəstində çoxlu sayda üsulla parçalamaq mümkündür. Dostlar artıq bunun neçə üsulla etmək mümkün olduğu haqqında düşünməyə başladılar. Onlara kömək etməyə çalışın.

Giriş verilənləri

İlk sətir nm (1n1000, 1m499500) tam ədədlərini ehtiva edir. Növbəti m sətrin hər biri qrafda i təpəsindən j təpəsinə istiqamətlənmiş tilin olduğunu ifadə edən iki tam ij tam ədədlərini ehtiva edir.

Çıxış verilənləri

Yeganə ədədi – məsələnin cavabını 109 + 7 moduluna görə çap edin.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
3 3
1 2
2 3
1 3
Çıxış verilənləri #1
2