Kaktusun yubileyi

Bu 20-ci Şimal-Şərqi Avropa regionu (NEERC) yarışmasıdır. Kaktus tapşırıqları NEERC-in ənənəsinə çevrilib. İlk kaktus tapşırığı 2005-ci ildə olub, buna görə də bu gün kaktusun 10 illik yubileyidir.

Kaktus, hər bir kənarın ən çox bir dövrədə yerləşdiyi əlaqəli istiqamətsiz qrafdır. İntuisiya ilə kaktus, bəzi dövrələrin icazə verildiyi ağacın ümumiləşdirilməsidir. Kaktusda çoxkənarlar (bir cüt zirvə arasında bir neçə kənar) və döngələr (zirvəni özü ilə birləşdirən kənarlar) icazə verilmir.

Sizə kaktus verilib. Gəlin bir kənarı yerini dəyişək - qrafdan bir kənarı silək və başqa bir zirvə cütünü kənarla birləşdirək ki, qraf kaktus olaraq qalsın. Belə kənar dəyişmələrinin neçə variantı mövcuddur?

Məsələn, yuxarıdakı sol kaktusda (birinci nümunədə verilmiş) 42 kənar dəyişmə variantı mövcuddur. Sağ kaktusda (ikinci nümunədə verilmiş), NEERC 2005-dən bəri standart kaktus nümunəsi olan, dəqiq 216 kənar dəyişmə variantı mövcuddur.

Giriş məlumatları

Birinci sətir iki tam ədəd n və m (1 ≤ n ≤ 50 000, 0 ≤ m ≤ 50 000) ehtiva edir. Burada n qrafdakı zirvələrin sayıdır. Zirvələr 1-dən n-ə qədər nömrələnib. Kənarlar kənarlarla kəsişməyən yollar dəstəsi ilə verilir, burada m belə yolların sayıdır.

Növbəti m sətirin hər biri qrafda bir yol ehtiva edir. Yol k[i] (2 ≤ k[i] ≤ 1000) ədədi ilə başlayır, ardınca 1-dən n-ə qədər k[i] tam ədəd gəlir. Bu k[i] ədədlər yoldakı qrafın zirvələrini təmsil edir. Yoldakı qonşu zirvələr fərqlidir. Yol bir zirvədən bir neçə dəfə keçə bilər, lakin hər bir kənar yalnız bir dəfə rast gəlinir.

Nümunədəki qraf kaktusdur.

Çıxış məlumatları

Bir ədəd çıxarın - kaktusda kənarı yerini dəyişməyin variantlarının sayı.