Quân xe tô màu

Cho $n$ màu và $m$ cặp màu hòa hợp với nhau. Bạn cần đặt một số quân xe lên bàn cờ kích thước ${10}^9\times {10}^9$, mỗi quân được tô một trong $n$ màu, sao cho:

• Mỗi màu xuất hiện ít nhất một quân xe trên bàn.
• Với mỗi màu, tập các quân xe cùng màu đó là liên thông.
• Với hai màu phân biệt $a$ và $b$ bất kỳ, hợp của tập quân xe màu $a$ và tập quân xe màu $b$ là liên thông khi và chỉ khi cặp $(a,b)$ hòa hợp.

Một tập quân xe được gọi là liên thông nếu từ một quân xe bất kỳ trong tập có thể đi tới mọi quân xe khác của tập, mỗi bước nhảy chỉ tới một quân xe khác cùng tập nằm trên cùng hàng hoặc cùng cột (xe có thể "nhảy qua" các quân khác).

Tổng số quân xe sử dụng không được vượt quá $5000$.

Bài đảm bảo có nghiệm với mọi dữ liệu vào hợp lệ. Nếu có nhiều cách đặt thỏa mãn, in ra bất kỳ cách nào.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$ — số lượng màu và số cặp màu hòa hợp.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên phân biệt — chỉ số hai màu hòa hợp. Không có cặp nào xuất hiện hai lần.

Dữ liệu ra

In ra $n$ khối. Khối thứ $i$ mô tả các quân xe màu $i$:

• Dòng đầu của khối là số nguyên $a_i$ ($1\le a_i\le 5000$) — số quân xe màu $i$.
• $a_i$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x$ và $y$ ($1\le x,y\le {10}^9$) — toạ độ một quân xe.

Tổng số quân xe trong toàn bộ output không vượt quá $5000$. Mọi quân xe phải nằm trên các ô khác nhau.

Ràng buộc

• $1\le n\le 100$
• $0\le m\le min(1000,{\displaystyle \frac{n(n-1)}{2}})$

Ví dụ