Connecting Two Barns

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ữ liệu vào

• 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$.

Dữ liệu ra

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

Ràng buộc

• $1\le T\le 20$.
• $1\le N\le {10}^5$, $0\le M\le {10}^5$.
• Tổng $N+M$ trên tất cả bộ test $\le 5\times {10}^5$.

Ví dụ