eolymp
bolt
Try our new interface for solving problems
Məsələlər

Maqnit yastıqlar

Maqnit yastıqlar

Gələcəyin şəhəri göydələnlərlə qurulub, göydələnlərarası hərəkət və nəqliyyatın parklanması üçün bir çox göydələn üçlüyü birqütblü maqnitlərdən ibarət üçbucaq yastıqlarla birləşdirilmişdir. Hər bir yastıq $3$ göydələni birləşdirir və yuxarıdan görünüşü təpə nöqtələri göydələnlərdə olan üçbucaq şəklindədir. Bu uyğun göydələnlər arasında maneəsiz dolaşmağa imkan verir. Yastıqları müxtəlif səviyyədə hazırlamaq olar, buna görə də bir göydələn digər cütlüklə müxtəlif yastıqlarla birləşdirilə bilər, belə ki, iki göydələn bir neçə yastıqla birləşdirilə bilər (müxtəlif göydələn üçlükləri ilə, həmçinin tək olanlarla). Məsələn $1, 2$ və $3$ nömrəli göydələnlər arasında və həmçinin $1, 2, 5$ arasında müxtəlif səviyyələrdə iki maqnit yastığı ola bilər. Maqnit yastıqları sistemi elə qurulub ki, onların köməyi ilə, bu şəhərdə bir göydələndən digərinə keçmək mümkündür (bir yastıqdan digərinə göydələnin daxilindən keçmək olar), lakin onların hər birinin saxlanılması böyük enerji hesabına başa gəlir. Elə proqram yazmaq tələb olunur ki, şəhərin maqnit yastığı sistemindən ləğv edilməməsi lazım gələn maqnit yastıqlarını təyin etsin, belə ki, hətta belə bir yastığın ləğv edilməsi ona gətirib çıxara bilər ki, elə göydələnlər tapılsın ki, onlardan bəzi digər göydələnlərə keçmək mümkün olmasın və bu da sakinlərin narahatlığına səbəb ola bilər. \InputFile Giriş faylının ilk sətrində şəhərdəki göydələnlərin və işləyən maqnit yastıqlarının sayını ifadə edən $n$ və $m~(3 \le n \le 10^5, 1 \le m \le 10^5)$ ədədləri verilir. Növbəti $m$ sətrin hər birində boşluqla ayrılmış üç ədəd --- yastıqla birləşdirilmiş göydələnlərin nömrələri verilir. Göydələnlər $1$-dən $n$-ə qədər ədədlərlə nömrələnir. Mövcud maqnit yastıqlarının bir göydələndən digərinə keçməyə imkan verdiyinə zəmanət verilir. \OutputFile Çıxış faylına əvvəlcə o maqnit yastıqlarının sayını verin ki, ayrılması şəhərə xəbərdar etmədən mümkün olmasın. Əgər bu ədəd sıfırdan fərqlidirsə, növbəti sətirdə boşluqla ayrılmış onların nömrəsini verin. Nömrələr maqnit yastıqlarının girişdə verilmiş ardıcıllığına uyğun gəlməlidir. Nömrələndirmə birdən başlayır. \includegraphics{https://static.e-olymp.com/content/19/19572f221bf485864bf0a882a3a8a83158a75528.gif}
Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
5 4
1 2 3
2 4 3
1 2 4
3 5 1
Çıxış verilənləri #1
1
4
Giriş verilənləri #2
3 2
1 2 3
3 2 1
Çıxış verilənləri #2
0
Giriş verilənləri #3
3 1
1 2 3
Çıxış verilənləri #3
1
1