Có \(n\) bạn sinh viên trong Câu lạc bộ Khoa học (CLB), trong đó có \(m\) cặp bạn bè quen nhau (theo thông tin mỗi thành viên tiết lộ). Hôm nay, trong buổi sinh hoạt CLB đầu tiên, bạn Hải - chủ nhiệm CLB muốn thành lập một số nhóm, và phân chia các bạn làm việc theo từng nhóm. Vì e sợ có những bạn chưa quen sẽ khó làm việc với nhau, Hải muốn phân chia sao cho trong mỗi nhóm không chứa hai bạn bất kì không quen nhau. Ngoài ra, Hải cũng muốn đảm bảo mỗi một cặp bạn trong số \(m\) cặp bạn quen nhau này đều thuộc về ít nhất một nhóm chung với nhau. Vì những yêu cầu đặc thù đó, có thể có những bạn sinh viên thuộc vào nhiều nhóm khác nhau. Câu hỏi đặt ra ở đây là Hải cần phải quản lý ít nhóm nhất có thể. Vậy, nên phân nhóm các bạn sinh viên như thế nào cho tối ưu?

Đây là một bài output-only (chỉ nộp kết quả đầu ra). Hãy chú ý các hướng dẫn dưới đây.

Input

• Thí sinh tải đầu vào tại đường dẫn: https://lqdoj.edu.vn/media/uploads/olp5scpartition_PmmCALo.zip
• Sau khi giải nén, bạn có 10 file đầu vào được đặt tên là 1.inp, 2.inp, 3.inp, ..., 9.inp, 10.inp, mỗi file mô tả một test theo định dạng sau:
  • Dòng đầu chứa hai số nguyên \(n, m\) (\(1 \leq n \leq 1000\), \(1 \leq m \leq \frac{n \cdot (n-1)}{2}\)). Các bạn sinh viên được đánh số thứ tự \(1, 2, 3, ..., n\).
  • Mỗi dòng trong số \(m\) dòng tiếp theo chứa hai số nguyên \(u, v\) (\(1 \leq u, v \leq n\)), nghĩa là \(u, v\) là bạn bè với nhau.

Output

Với mỗi file đầu vào i.inp bạn cần nộp file đầu ra i.out tương ứng (ví dụ file đầu vào là 7.inp thì file đầu ra là 7.out) theo định dạng:

• Dòng đầu chứa số \(k\) là số nhóm được lập ra.
• Dòng thứ \(i\) trong số \(k\) dòng tiếp theo ghi ra số \(c_i\) là số lượng bạn trong nhóm \(i\), tiếp theo sau là \(c_i\) số tương ứng là chỉ số của các bạn sinh viên trong nhóm này.
• Output phải đảm bảo tổng số thành viên trong các nhóm không quá 10 lần số cặp bạn bè trong Input tương ứng, nghĩa là \(\sum c_i \leq 10 \cdot m\).

Mỗi lần nộp bài bạn có thể nộp một hoặc nhiều file đầu ra, bạn cần nén các file đầu ra này lại thành submission.zip để nộp. Ở mục chọn ngôn ngữ của trang nộp bài, chọn "Output".

Example

4 5
1 2
4 3
1 3
3 2
2 4

2
3 2 3 4
3 1 2 3

Scoring

Đối với mỗi test bạn sẽ nhận được 0 điểm nếu đưa ra output không hợp lệ, ngược lại bạn sẽ nhận được điểm như sau: gọi \(k^*\) là số nhóm trong lời giải của ban giám khảo và \(k\) là số nhóm trong lời giải của bạn, điểm bạn nhận được cho mỗi test sẽ là: