Tối thiểu hóa cạnh

Điểm: 1,00 (OI)

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

Python 3 5.0s

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

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bessie có một đồ thị vô hướng liên thông $G$ gồm $N$ đỉnh (đánh số từ $1$ đến $N$ ) và $M$ cạnh. Đồ thị có thể chứa khuyên (cạnh nối một đỉnh với chính nó) nhưng không có cạnh song song.

Định nghĩa hàm $f_{G} (a, b)$ trả về giá trị đúng nếu tồn tại đường đi từ đỉnh $1$ đến đỉnh $a$ sử dụng đúng $b$ cạnh (mỗi cạnh có thể được đi qua nhiều lần).

Elsie cần xây dựng đồ thị $G^{'}$ sao cho $f_{G^{'}} (a, b) = f_{G} (a, b)$ với mọi giá trị $a$ và $b$ , đồng thời tối thiểu hóa số cạnh của $G^{'}$ .

Dữ liệu vào

Dòng đầu tiên chứa $T$ - số lượng bộ test.

Mỗi bộ test có dạng:

Dòng đầu: hai số nguyên $N$ và $M$ .
$M$ dòng tiếp theo: mỗi dòng chứa hai số nguyên $x$ và $y$ ( $1 \leq x \leq y \leq N$ ) mô tả một cạnh nối đỉnh $x$ và đỉnh $y$ .

Dữ liệu ra

Với mỗi bộ test, in ra số cạnh tối thiểu có thể có của $G^{'}$ trên một dòng.

Ràng buộc

$1 \leq T \leq 5 \cdot 10^{4}$
$2 \leq N \leq 10^{5}$
$N - 1 \leq M \leq \frac{N (N + 1)}{2}$
Tổng $N$ trên tất cả các bộ test $\leq 10^{5}$
Tổng $M$ trên tất cả các bộ test $\leq 2 \cdot 10^{5}$

Ví dụ

Input	Output	Giải thích
2 5 5 1 2 2 3 2 5 1 4 4 5 5 5 1 2 2 3 3 4 4 5 1 5	4 5	Bộ test 1: Có thể xây dựng $G^{'}$ với 4 cạnh mà vẫn giữ nguyên tính chất đường đi từ đỉnh 1. Ví dụ, cạnh $(2, 5)$ có thể được loại bỏ vì mọi đường đi qua cạnh này đều có thể thay thế bằng đường đi khác với cùng tính chẵn lẻ. Bộ test 2: Đồ thị gốc có một chu trình lẻ duy nhất (1-2-3-4-5-1), không thể loại bỏ cạnh nào mà giữ nguyên tính chất $f_{G}$ .

Ghi chú

Lưu ý rằng $G^{'}$ cũng là đồ thị vô hướng gồm $N$ đỉnh, có thể chứa khuyên và không có cạnh song song, nhưng không nhất thiết phải liên thông hay là đồ thị con của $G$ .

Bình luận

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