Detecting Cheaters

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Tác giả:
flo
Dạng bài
Điểm: 1100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Đúng rồi, tôi là một con người đã luôn có niềm đam mê với CP từ khi còn mới biết đi và biết nói. Và cũng từ đó, tôi đã quyết tâm trao dồi kiến thức CP một cách nghiêm túc và trung thực bằng cách học thêm các thuật toán mới lạ cùng với đó là làm các cuộc thi trên các OJ. Không biết bao nhiêu ngày, bao nhiêu tháng đã trôi qua, sự nỗ lực và lòng quyết tâm của tôi đã được đền đáp khi tôi rất giỏi CP cùng với rất nhiều thành tích đáng tự hào khiến bao nhiêu ánh mắt chỉ biết nhìn rồi nể phục. Vì đã bỏ ra nhiều công sức như thế, tôi rất ghét những người có hành vi gian lận với những thứ liên quan đến CP.

Đó là một ngày đẹp trời, tôi đang tìm kiếm một OJ mới nào đó để luyện tập. Bằng một cách thần kỳ nào đó, LQDOJ đã lọt vào trong con mắt tìm kiếm của tôi. Thế là tôi đã đưa ra một quyết định là di chuyển con chuột và nhấp vào OJ ấy vì muốn biết ở đây có những gì. Đúng, tôi đã vô cùng ngạc nhiên khi nơi đây có rất nhiều bài tập phong phú được tự tay viết và tham khảo lấy về từ một số OJ uy tín khác. Ngoài ra, các cuộc thi cũng được tổ chức khá là nhiều, tạo điều kiện cho những CP-er như tôi có thể tham gia và làm để biết thực lực của mình tới đâu. Sự ấn tượng của tôi ngày càng tăng bởi từ bất ngờ này đến bất ngờ nọ cho đến lúc bảng xếp hạng của một số cuộc thi được tôi bật lên, tôi đã rất là sốc khi số lượng kẻ gian lận quá nhiều và không còn đếm trên đầu ngón tay nữa. Như đã kể ở trên và từ đó, tôi đã ghim những cái tên được tô màu đỏ đó với một suy nghĩ là xóa sổ chúng ra khỏi đây một ngày nào đó không xa.

Hôm nay, tôi vào LQDOJ để xem có gì mới không thì bỗng thấy một bài viết của admin thông báo rằng LQDOJ Contest #11.5 sắp được tổ chức. Vậy là tôi đã không do dự gì mà quyết định sẽ tham gia làm. Bỗng tôi nhớ đến những kẻ gian lận mà tôi thấy từ những ngày đầu tiên biết đến LQDOJ. Vậy là tôi quyết định khi các bài của cuộc thi được công khai, tôi sẽ kiểm tra bài nộp của bọn đấy thật kĩ để xem liệu bọn chúng có gian lận hay không. Sau đó, tôi sẽ báo cáo với admin và chờ đợi tài khoản của bọn chúng bị cấm vĩnh viễn ở LQDOJ.

Rồi chuyện gì đến cũng sẽ đến, LQDOJ Contest #11.5 ghi nhận số lượng thí sinh tham gia lên đến \(n\) thí sinh. Con số đấy quá lớn khiến tôi đã mất một hồi rất lâu để kiểm tra những kẻ gian lận, và rồi cuối cùng, tôi cũng đã thu thập được \(m\) cặp bài nộp đáng nghi nhất. Trong số đó, cặp bài nộp thứ \(i\) là của \(2\) thí sinh khác nhau có số thứ tự là \(u_i\) và \(v_i\), và khả năng cao là \(2\) thí sinh này đã chép code nhau. Chính vì điều này, nếu \(2\) thí sinh \(i\) và \(j\) chép code nhau và \(2\) thí sinh thứ \(j\) và \(k\) chép code nhau, khả năng cao là \(2\) thí sinh thứ \(i\) và \(k\) cùng sử dụng chung một code. Để tiện cho các admin, tôi quyết định chia những kẻ gian lận này vào các nhóm với những người trong cùng một nhóm có khả năng cao là sử dụng chung một code. Tuy nhiên, việc tìm kiếm và kiểm tra đã khiến tôi vô cùng mệt mỏi nên tôi không thể làm điều này được nữa. Là một CP-er chân chính và không phải là một kẻ gian lận (hay chép code của người khác rồi tỏ ra mình là một con người giỏi giang và sống trên thành tích ảo, trong khi chỉ là một con gà bị ngáo và thèm khát danh tiếng), bạn hãy giúp tôi làm điều này nhé. Cảm ơn!

Input

  • \(2\) số nguyên dương \(n, m\) \((1 \le n \le 10^9; 1 \le m \le 10^5)\).
  • \(m\) dòng tiếp theo, mỗi dòng là \(2\) số nguyên dương \(u_i, v_i\) \((1 \le u_i, v_i \le n; u_i \ne v_i)\).

Output

  • In ra một số nguyên dương \(k\) là số nhóm được chia ra.
  • \(k\) khối tiếp theo, khối thứ \(i\) sẽ gồm \(2\) dòng như sau:
    • Số nguyên dương \(c\) là số lượng thí sinh trong nhóm thứ \(i\).
    • Dãy tăng \(a\) gồm \(c\) phần tử \(a_1, a_2, ..., a_c\) là thứ tự của các thí sinh thuộc nhóm thứ \(i\).
  • Các nhóm phải được in ra theo thứ tự từ điển của các dãy \(a\).

Scoring

  • Subtask \(1\) \((30\%)\): \(1 \le n, m \le 10^3\).
  • Subtask \(2\) \((30\%)\): \(1 \le n \le 10^5\).
  • Subtask \(3\) \((40\%)\): Không giới hạn gì thêm.

Test

Input 
6 3
1 2
3 2
4 5
Output 
2
3
1 2 3
2
4 5

Bình luận