Düşmənlərin bölünməsi

Kapitan Keram çətin bir qərar verməlidir. 2147-ci ildir və dünyada böyük bir müharibə gedir. Onun əsgərləri müharibənin əvvəlində, iki il əvvəl birlikdə idilər, lakin indi bəziləri düşmənə çevrilib. Xoşbəxtlikdən, hər bir əsgərin ən çox 3 düşməni var.

Onlar yaxın zamanda başqa bir ölkəyə hücum etməlidirlər və Keram düşmən olan əsgərlərin döyüş zamanı uğurla əməkdaşlıq edə bilməyəcəyindən narahatdır. O, əsgərləri elə qruplara bölmək istəyir ki, hər bir əsgərin öz qrupunda ən çox bir düşməni olsun. O, sadə bir həll tapmaq istəyir, buna görə də mümkün qədər az sayda qrupdan istifadə etmək istəyir. Siz onun üçün əsgərləri qruplara bölə bilərsinizmi?

Giriş məlumatları

Birinci sətir iki tam ədəd n və m (2 ≤ n ≤ 100000, 0 ≤ m ≤ 3n/2) ehtiva edir, burada n - əsgərlərin sayı, m - düşmən cütlərinin sayı. Növbəti m sətirin hər biri a[i], b[i] (1 ≤ a[i] < b[i] ≤ n) tam ədədlərini ehtiva edir - düşmən olan əsgərlərin nömrələri. Hər bir əsgərin ən çox 3 düşməni olduğunu nəzərə alın.

Çıxış məlumatları

Birinci sətirdə əsgərlərin ən az sayda qruplara bölünməsi üçün k ədədini çıxarın. Növbəti k sətirin hər biri hər qrupdakı əsgərlərin siyahısını ehtiva etməlidir.