Phản công

Cho một đồ thị vô hướng đơn $G$ trên $N$ đỉnh được mô tả bởi danh sách $M$ cạnh. Xét đồ thị bù $\bar{G}$ của $G$: $\bar{G}$ có cùng tập đỉnh, và hai đỉnh phân biệt $u,v$ kề nhau trong $\bar{G}$ khi và chỉ khi $u,v$ không kề nhau trong $G$.

Hãy tìm các thành phần liên thông của $\bar{G}$ — tức là phân hoạch tập $\{1,2,\dots ,N\}$ thành các nhóm sao cho hai đỉnh thuộc cùng một nhóm khi và chỉ khi tồn tại đường đi giữa chúng trong $\bar{G}$.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N$ và $M$ — số đỉnh và số cạnh của $G$.

$M$ dòng sau, dòng thứ $i$ chứa hai số nguyên $a_i,b_i$ ($a_i\ne b_i$) — mô tả cạnh thứ $i$ trong $G$. Không có cặp cạnh nào trùng lặp.

Dữ liệu ra

Dòng đầu in một số nguyên $k$ — số thành phần liên thông của $\bar{G}$.

$k$ dòng tiếp theo, mỗi dòng mô tả một thành phần: số đầu là $t_i$ (số đỉnh trong thành phần), tiếp theo là $t_i$ chỉ số đỉnh thuộc thành phần đó, cách nhau bởi dấu cách.

Thứ tự các thành phần và thứ tự các đỉnh trong mỗi thành phần không quan trọng. Tổng $\sum t_i$ phải bằng $N$.

Ràng buộc

• $1\le N\le 5·{10}^5$
• $0\le M\le {10}^6$
• $1\le a_i,b_i\le N$, $a_i\ne b_i$

Ví dụ