Connecting Two Barns

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.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

FJ có $N$ cánh đồng (đánh số từ $1$ đến $N$ ) và $M$ con đường hai chiều nối các cặp cánh đồng. Hai chuồng bò nằm ở cánh đồng $1$ và cánh đồng $N$ .

FJ muốn xây thêm tối đa $2$ con đường mới để cánh đồng $1$ và $N$ liên thông. Chi phí xây đường nối cánh đồng $i$ và $j$ là $(i - j)^{2}$ .

Hãy tìm tổng chi phí nhỏ nhất.

Dòng $1$ : Số nguyên $T$ — số bộ test.
Với mỗi bộ test:
- Dòng $1$ : Hai số nguyên $N$ và $M$ .
- $M$ dòng tiếp: Mỗi dòng gồm hai số nguyên $i$ và $j$ — đường nối $i$ và $j$ .

In $T$ dòng, mỗi dòng là chi phí nhỏ nhất của bộ test tương ứng.

Input	Output	Giải thích
2 5 2 1 2 4 5 5 3 1 2 2 3 4 5	2 1	Bộ test 1: nối $(2, 3)$ và $(3, 4)$ với chi phí $1 + 1 = 2$ . Bộ test 2: nối $(3, 4)$ với chi phí $1$ .

Bình luận

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