Trang trại của Farmer John gồm \(N\) cánh đồng (\(1 \leq N \leq 10^5\)), được đánh số thuận tiện từ \(1 \ldots N\). Giữa các cánh đồng có \(M\) đường đi hai chiều (\(0 \leq M \leq 10^5\)), mỗi đường nối một cặp cánh đồng.

Trang trại có hai nhà kho, một ở cánh đồng \(1\) và một ở cánh đồng \(N\). Farmer John muốn đảm bảo có thể đi bộ giữa hai nhà kho theo một dãy đường đi nào đó. Ông sẵn sàng xây thêm tối đa hai đường đi để đạt được mục tiêu này. Do cách bố trí các cánh đồng, chi phí xây một đường đi mới giữa cánh đồng \(i\) và \(j\) là \((i-j)^2\).

Hãy giúp Farmer John xác định chi phí nhỏ nhất cần thiết để hai nhà kho \(1\) và \(N\) có thể đi tới nhau.

Dữ liệu vào

Mỗi dữ liệu vào chứa \(T\) bộ dữ liệu con (\(1\le T\le 20\)), tất cả đều phải được giải đúng để giải được toàn bộ dữ liệu.

Dòng đầu tiên chứa \(T\), sau đó là \(T\) bộ dữ liệu con.

Mỗi bộ dữ liệu con bắt đầu bằng hai số nguyên \(N\) và \(M\). Tiếp theo là \(M\) dòng, mỗi dòng chứa hai số nguyên \(i\) và \(j\), biểu thị một đường đi giữa hai cánh đồng khác nhau \(i\) và \(j\). Đảm bảo rằng giữa hai cánh đồng bất kỳ có nhiều nhất một đường đi và tổng \(N+M\) trên tất cả các bộ dữ liệu con không vượt quá \(5 \cdot 10^5\).

Dữ liệu ra

In ra \(T\) dòng. Dòng thứ \(i\) chứa một số nguyên duy nhất là chi phí nhỏ nhất cho bộ dữ liệu con thứ \(i\).

Phân nhóm

• Dữ liệu 2: \(N \le 20\).
• Dữ liệu 3–5: \(N \le 10^3\).
• Dữ liệu 6–10: Không có ràng buộc bổ sung.

Ví dụ

2
5 2
1 2
4 5
5 3
1 2
2 3
4 5

2
1

Nguồn

USACO 2021 December Contest, Silver — Connecting Two Barns. Tác giả: Nick Wu.

https://usaco.org/index.php?page=viewproblem2&cpid=1159