Kaktus#5351
Kaktus, hər bir kənarı ən çox bir dövrədə yerləşən əlaqəli istiqamətsiz qrafdır. İntuisiya ilə desək, kaktus bəzi dövrələrin icazə verildiyi ağacın ümumiləşdirilmiş formasıdır. Sizdən verilmiş qrafın kaktus olub-olmadığını yoxlamaq tələb olunur. Kaktusun ağacdan əsas fərqi ondadır ki, kaktusda bəzi ostov altqraflar da kaktus ola bilər. Belə altqrafların sayı (qrafın özü də daxil olmaqla) qrafın kaktusluğunu müəyyən edir (ağac üçün bu ədəd birlikdir). Kaktus olmayan qrafın kaktusluğu sıfıra bərabərdir.
Şəkildəki birinci qrafın kaktusluğu 35-ə bərabərdir. İkinci qraf kaktus deyil, çünki (2, 3) kənarı iki dövrədə yerləşir. Üçüncü qraf kaktus deyil, çünki o, əlaqəsizdir.
Birinci sətir iki tam ədəd n və m (1 ≤ n ≤ 20000, 0 ≤ m ≤ 1000) ehtiva edir. Burada n qrafın zirvələrinin sayıdır. Zirvələr 1-dən n-ə qədər nömrələnmişdir. Qrafın kənarları kənarlarla kəsişməyən yollar çoxluğu ilə təqdim olunur, burada m belə yolların sayıdır.
Növbəti m sətirin hər biri qrafda bir yol ehtiva edir. Yol tam ədəd k[i] (2 ≤ k[i] ≤ 1000) 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 yolun zirvələrini təyin edir. Yol bir zirvədən bir neçə dəfə keçə bilər, lakin hər bir kənar bütün giriş məlumatlarında yalnız bir dəfə veriləcək. Qraf çoxkənarlı deyil (zirvə cütü arasında bir kənardan çox kənar yoxdur).
Bir ədəd çıxarın - qrafın kaktusluğunu. Qeyd edək ki, kaktusluq böyük bir ədəd ola bilər.
Nümunə 1