Poçtalyon Xanım

Ledi məktəbdən sonra poçtalyon kimi işləyir. Bu iş Ledi üçün çox maraqlıdır və o, artıq uzun müddətdir ki, bu sahədə çalışır. Ledi şəhərdəki ən təcrübəli poçtalyondur və məktubların vaxtında çatdırılmasına nəzarət edir, həmçinin poçtalyonlar üçün marşrutlar qurur.

Ledi'nin yaşadığı şəhər poçt bölgələrinə bölünür. Hər bir poçt bölgəsi, sakinlərin evlərinin yerləşdiyi kəsişmələri birləşdirən yollar şəbəkəsinə malikdir. Hər bir yoldan hər iki istiqamətdə keçmək mümkündür. Hər bölgədə poçt xidmətlərində işləmək üçün istənilən sayda insan qəbul edilə bilər.

Hər səhər, hər poçtalyon bölgənin bəzi küçələrindən keçən marşrut boyunca çatdırılmalı olan məktublarla dolu bir çanta alır. Hər bir marşrut Ledi'nin müəyyən etdiyi şərtlərə cavab verməlidir:

1. Marşrut eyni kəsişmədə başlayıb bitməlidir.

2. Marşrut heç vaxt eyni kəsişmədən iki dəfə keçməməlidir.

3. Marşrutun heç bir yolu başqa bir marşrutla ortaq olmamalıdır. Yəni hər bir yolu yalnız bir poçtalyon istifadə etməlidir.

Bütün poçtalyonlar birlikdə bölgəni tamamilə xidmət etməlidirlər. Hər bir yol yalnız bir marşruta aid olmalıdır.

Ledi poçtalyonların marşrutlarının qurulmasına cavabdehdir və istənilən sayda poçtalyon işə qəbul edə bilər. O, sizdən müəyyən poçt bölgələri üçün poçtalyonların bütün şərtlərə cavab verəcək marşrutlar dəstini tapmağınızı xahiş edir.

Giriş verilənləri

Birinci sətir iki tam ədədi $n$ və $m$ ($3\le n\le 5\cdot 10^5$, $3\le m\le 5\cdot 10^5$) — kəsişmələrin və yolların sayını ehtiva edir.

Növbəti $m$ sətirin hər biri iki tam ədəd $u$ və $v$ ($1\le u,v\le n,u\ne v$) ehtiva edir — aralarında yol olan kəsişmələr.

Giriş məlumatlarında aşağıdakı şərtlər yerinə yetirilir:

1. İstənilən iki kəsişmə arasında ən çox bir yol var.

2. İstənilən iki kəsişmə arasında bir və ya daha çox yoldan keçə bilən bir yol mövcuddur.

3. Həll mövcuddur, yəni Ledi həmişə bütün şərtlərə cavab verən marşrutlar dəsti tapa bilər.

Çıxış verilənləri

Birinci sətirdə bir tam ədəd $d$ ($1\le d\le m$) — marşrutların sayını çıxarın.

Növbəti $d$ sətirin hər birində bir tam ədəd $w$ ($1\le w\le m$) — marşrutdakı kəsişmələrin sayını çıxarın, sonra isə $w$ tam ədəd $l_1,l_2,\dots ,l_w$ ($1\le l_i\le n$) çıxarın — kəsişmələrin nömrələri. Kəsişmələr poçtalyonun onları keçəcəyi sırada çıxarılmalıdır. Poçtalyonun marşrutunun başladığı və bitdiyi kəsişmə yalnız bir dəfə marşrutun başlanğıcında çıxarılmalıdır.

Əgər bir neçə həll mövcuddursa, proqramınız istənilən birini çıxara bilər.

Nümunələr

Qiymətləndirmə

1. ($38$ bal): $3\le n\le 2000,3\le m\le 10^5$;

2. ($17$ bal): $3\le n\le 10^5,3\le m\le 10^5$;

3. ($45$ bal): $3\le n\le 5\cdot 10^5,3\le m\le 5\cdot 10^5$.