Quân xe tô màu

Điểm: 5,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

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 \leq a_{i} \leq 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 \leq x, y \leq 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 \leq n \leq 100$
$0 \leq m \leq min (1000, \frac{n (n - 1)}{2})$

Ví dụ

Input	Output	Giải thích
3 2 1 2 2 3	2 1 1 1 4 3 2 2 2 4 2 5 2 3 3 3 5	Cặp $(1, 2)$ liên thông qua cột 4; cặp $(2, 3)$ liên thông qua cột 5. Màu 1 và màu 3 không chia sẻ hàng hay cột nào. Bài có thể có nhiều cách đặt khác cùng thỏa mãn.
3 3 1 2 2 3 3 1	3 1 1 1 4 1 6 3 2 2 2 4 2 5 3 3 3 3 5 3 6	Cặp $(1, 2)$ chia sẻ cột 4; cặp $(2, 3)$ chia sẻ cột 5; cặp $(1, 3)$ chia sẻ cột 6 — mọi cặp đều liên thông.
3 1 1 3	2 1 1 1 4 1 2 2 2 3 3 3 4	Chỉ có cặp $(1, 3)$ hòa hợp — chúng chia sẻ cột 4. Màu 2 đứng độc lập tại $(2, 2)$ , không liên thông với màu nào khác.

Bình luận

Không có bình luận tại thời điểm này.