Quản lý vùng BALLAS

Xem PDF

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Sau khi thanh toán hết băng nhóm BALLAS, CJ đã tịch thu những nơi do băng BALLAS làm chủ. Là một trong những người đứng đầu nhóm GROVE STREET FAMILIES, nên CJ đã ra lệnh cho một số lính thăm dò về vùng đất bị thu hồi này. Sau khi thăm dò, thì CJ biết trong vùng có \(N\) ngôi nhà, đánh số từ \(1\) tới \(N\), và có \(M\) tuyến đường giao thông hai chiều nối trực tiếp hai ngôi nhà với nhau. Lúc này CJ ra lệnh cho một số lính quản lý vùng đã được thu hồi với các điều kiện sau:

  • Mỗi ngôi nhà chỉ chịu quản lý của một lính của CJ.
  • Tập hợp các ngôi nhà có thể kết nối được với nhau (bất kỳ hai ngôi nhà nào cũng có thể kết nối với nhau) thì cũng chỉ chịu quản lý bởi một lính của CJ.
  • Định nghĩa ngôi nhà \(u\) với ngôi nhà \(v\) kết nối được với nhau là tồn tại một đường đi giữa hai ngôi nhà \(u\)\(v\), tức là tồn tại dãy các ngôi nhà \(P=⟨u = p_0 , p_1 ,…, p_k = v⟩\) sao cho \(∀i:1 \lt i \leq k\) thì tồn tại tuyến đường trực tiếp giữa hai ngôi nhà \(p_i−1\)\(p_i\) trong khu vực.
  • Số lính quản lý là ít nhất.

Yêu cầu: hãy tìm số lính quản lý thoả mãn các điều kiện của CJ, và chỉ ra rõ ra những ngôi nhà mà từng lính quản lý. Nếu có nhiều cách quản lý, chỉ ra một cách bất kì.

Input

  • Gồm \(M+1\) dòng:
    • Dòng đầu tiên chứa 2 số nguyên dương \(N, M\).
    • \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u, v\) thể hiện có tuyến đường hai chiều nối trực tiếp từ ngôi nhà \(u\) tới ngôi nhà \(v\) trong vùng.

Output

  • Gọi \(K\) là số đàn em quản lý thoả mãn các điều kiện của CJ. Ghi ra \(K+1\) dòng:

    • Dòng đầu tiên ghi ra số nguyên dương \(K\).
    • \(K\) dòng tiếp theo, dòng thứ \(i\) ghi ra số đầu tiên là số \(X\) - số ngôi nhà do lính \(i\) quản lý, \(X\) số tiếp theo là số hiệu ngôi nhà do lính \(i\) quản lý.

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10 ^ 3, M \leq 10 ^ 4\).
  • Subtask \(2\) (\(70\%\) số điểm): \(N \leq 10 ^ 5, M \leq 10 ^ 6\).

Example

Test 1

Input
12 10
1 4
2 3
3 6
4 5
6 7
8 9
8 10
9 11
11 8
11 12 
Output
3
3 1 4 5 
4 2 3 6 7 
5 8 9 10 11 12

Bình luận


  • 1
    huyhau6a2 7:58 a.m. 15 Tháng 3, 2022

    mất 3 lần nộp vì quên ios