E. Сөрөг довтолгоон

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Бэрландчууд Флатландынхны довтолгооныг эсэргүүцсэн бөгөөд одоо сөрөг довтолгооноо эхлэж байна.

Флатланд $1$-ээс $n$ дугаар бүхий $n$ хоттой ба тэдний зарим хос нь $2$ чиглэлт замаар холбогдсон байдаг. Флатландын газрын зурагт хотуудын хоорондох замыг дүрсэлсэн байх гарцаагүй бөгөөд хүрэлцээтэй нөхцөл нь тэнд үнэндээ зам байдаггүй байх юм. Өөрөөр хэлбэл газрын зурагт тухайн хос хотыг холбосон зам байвал үнэндээ тэнд зам байхгүй гэсэн үг юм. Эсрэг тохиолдол мөн үнэн: Хэрэв $2$ хот газрын зураг дээр замаар холбогдоогүй бол үнэндээ тэд холбогдсон байх юм.

Бэрландчууд Флатландын газрын зургийг. Васиа дараах нөхцлийн хангах хотуудын груп болгонг олохоор томилогдов: груп бүрт аль ч хотоос нөгөө хотруугаа явсан замтай. Мөн өөр группын хотуудруу явах зам байхгүй. Үнэндээ группуудыг устгасан нь бүхэл улсыг эзлэхээс хамаагүй хялбар юм.

Васиад даалгаврыг нь биелүүлэхэд нь туслаарай. Флатландын газрын зурагт хотуудын хоорондох замыг дүрсэлсэн байх гарцаагүй бөгөөд хүрэлцээтэй нөхцөл нь тэнд үнэндээ зам байдаггүй болохыг бүү мартаарай.

Оролт

Эхний мөрөнд $n$ ба $m$ $(1 ≤ n ≤ 5*10^{5}, 0 ≤ m ≤ 10^{6})$ байрлана -- хотуудын тоо ба газрын зураг дээр дүрсэлсэн замын тоо

Дараагийн $m$ мөрөнд газрын зургандээрх дүрслэлийг харуулна. $i$ дугаар мөрөнд 2 бүхэл тоо $a_{i}$ ба $b_{i}$ $(1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i})$ байна -- газрын зурган дээр $i$ дүгээр замаар холбогдсон хотуудын дугаар.

Хотуудын хос нь оролтын файланд 1-ээс олонгүй удаа орно.

Гаралт

Эхний мөрөнд $k$ тоог хэвлэ. -- дээрх нөхцөлийг хангасан группын тоо.

дараагийн $k$ мөр бүрт эхлээд $i$ дэх группдэх оройн тоо $t_{i}$ $(1 ≤ t_{i} ≤ n)$ -ийг хэвлэн түүнд байгаа хотуудын дугаарыг зайгаар тусгаарлан хэвлэ.

Групп болон хотуудыг хэвлэх дараалал дурын байж болно. Нийт $t_{i}$-үүдийн нийлбэр нь $n$ байх ёстой.

Орчуулсан: Бат-Од

Жишээ тэстүүд

Оролт
4 4
1 2
1 3
4 2
4 3
Гаралт
2
2 1 4 
2 2 3 
Оролт
3 1
1 2
Гаралт
1
3 1 2 3 

Тэмдэглэл

Эхний жишээн дээр 1-4 2-3 гэсэн л замууд бий.

Дараагийн жишээн дээр 1-2 гэсэн зам байхгүй боловч аль нэгнээс нь 3 дугаар хотыг дамжин нөгөөд нь хүрч чадах юм.

Сэтгэгдлүүдийг ачааллаж байна...