e-olymp
Məsələlər

Yenidənqurma

Yenidənqurma

Hansısa bir ölkədə n sayda şəhər və onlar arasında m yol var. Bu zaman bu ölkədə yol sistemi növbəti şəkildə qurulmuşdur:

  • istənilən iki şəhər arasında yolların sayı birdən çox deyildir;
  • Heç bir yol şəhəri özü ilə birləşdirmir.

Hakimiyyət dəyişikliyindən sonra yeni hökumət bir sıra islahatlar aparmaq qərarına gəldi. Bu islahatlar arasında ölkənin yol sisteminə də toxunanı vardı. Bu islahat iki bənddən ibarətdir:

  • mövcud yollardan birini dağıtmaq;
  • əvvəlcədən mövcud olmayan, şəhərin özünə aparmayan yeni yol seçmək.

Bundan başqa, şəhərlər arasında iqtisadi əlaqələri yaxşılaşdırmaq üçün hökumət istəyir ki, yol islahatı qəbul edildikdən sonra istənilən şəhərə istənilən yolla getmək mümkün olsun. Bu zaman bu tələbin islahatdan öncə yerinə yetirilmiş olduğuna zəmanət verilmir.

İndi hökumət islahatın həyata keçirilməsi üçün neçə variantın olduğu haqqında düşünür. Ona kömək edin.

Giriş verilənləri

Birinci sətir iki nm (1n100000, 0m200000) tam ədədlərini ehtiva edir. Növbəti m sətir iki aibi (1ai, bin, aibi) ədədlərini — i-ci yolun birləşdirdiyi şəhərlərin nömrələrini ehtiva edir.

Çıxış verilənləri

İslahat keçirmək üçün variantların sayını təyin edən yeganə tam ədədi verin.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri
4 4
1 2
2 3
1 3
3 4
Çıxış verilənləri
8
Параллелепипед
Война