Mocha và Diana

Điểm: 4,00 (OI)

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

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

Một rừng là một đồ thị vô hướng không có chu trình (không bắt buộc liên thông).

Mocha và Diana đều có một rừng với $n$ đỉnh được đánh số từ $1$ đến $n$ . Họ muốn thêm các cạnh vào rừng của mình sao cho:

Sau khi thêm, cả hai đồ thị vẫn là rừng (không xuất hiện chu trình).
Họ phải thêm các cạnh giống hệt nhau: nếu cạnh $(u, v)$ được thêm vào rừng của Mocha thì cạnh $(u, v)$ cũng được thêm vào rừng của Diana, và ngược lại.

Hãy tìm số lượng cạnh tối đa có thể thêm và liệt kê các cạnh đó.

Dữ liệu vào

Dòng đầu chứa ba số nguyên $n$ , $m_{1}$ , $m_{2}$ ( $1 \leq n \leq 1000$ ; $0 \leq m_{1}, m_{2} < n$ ) — số đỉnh và số cạnh ban đầu trong rừng của Mocha và Diana.
$m_{1}$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$ và $v$ ( $1 \leq u, v \leq n$ ; $u \neq v$ ) — một cạnh trong rừng của Mocha.
$m_{2}$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$ và $v$ ( $1 \leq u, v \leq n$ ; $u \neq v$ ) — một cạnh trong rừng của Diana.

Dữ liệu đảm bảo cả hai đồ thị ban đầu đều là rừng.

Dữ liệu ra

Dòng đầu chứa một số nguyên $h$ — số cạnh tối đa có thể thêm.
$h$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$ và $v$ ( $1 \leq u, v \leq n$ ; $u \neq v$ ) — cạnh thứ $i$ được thêm.

Nếu có nhiều đáp án thỏa mãn, in ra bất kỳ.

Ví dụ

Input	Output	Giải thích
8 1 2 1 7 2 6 1 5	5 1 2 1 3 1 4 1 8 5 7	Có thể thêm $5$ cạnh sao cho cả hai rừng vẫn không có chu trình. Đây là một đáp án hợp lệ; vẫn còn nhiều đáp án khác.
5 3 2 5 4 2 1 4 3 4 3 1 4	1 1 5	Rừng Mocha có hai thành phần ${1, 2}$ và ${3, 4, 5}$ ; rừng Diana có hai thành phần ${1, 3, 4}$ và ${2}$ với một đỉnh $5$ cô lập. Cạnh $(1, 5)$ nối hai thành phần trong cả hai rừng mà không tạo chu trình.
3 2 2 1 2 2 3 1 2 1 3	0	Rừng Mocha là chuỗi $1 - 2 - 3$ , rừng Diana cũng là cây gồm cạnh $1 - 2$ và $1 - 3$ . Cả hai đã liên thông nên không thể thêm cạnh nào.

Bình luận

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