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 là $1 \ldots N$. Giữa các cánh đồng có $M$ con đường 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 chuồng bò, một ở cánh đồng $1$ và một ở cánh đồng $N$. Farmer John muốn bảo đảm có thể đi bộ giữa hai chuồng bò theo một dãy các con đường. Ông sẵn sàng xây thêm tối đa hai con đường mới để đạt được mục tiêu này. Do vị trí của các cánh đồng, chi phí xây một con đường 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 để có thể đi từ chuồng bò $1$ đến chuồng bò $N$ và ngược lại.

Dữ liệu vào

Mỗi bộ kiểm thử đầu vào chứa $T$ trường hợp con ($1\le T\le 20$), và phải giải đúng tất cả chúng để vượt qua bộ kiểm thử đầu vào đó.

Dòng đầu tiên của đầu vào chứa $T$, sau đó là $T$ trường hợp kiểm thử con.

Mỗi trường hợp kiểm thử 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 con đường giữa hai cánh đồng khác nhau $i$ và $j$. Bảo đảm rằng có nhiều nhất một con đường giữa hai cánh đồng bất kỳ và tổng $N+M$ trên tất cả các trường hợp kiểm thử con không vượt quá $5 \cdot 10^5$.

Dữ liệu ra

In ra $T$ dòng. Dòng thứ $i$ phải chứa một số nguyên duy nhất biểu thị chi phí nhỏ nhất cho trường hợp kiểm thử con thứ $i$.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

2
1

Ghi chú

Trong trường hợp kiểm thử con đầu tiên, phương án tối ưu là nối cánh đồng $2$ và $3$ bằng một con đường, rồi nối cánh đồng $3$ và $4$ bằng một con đường.

Trong trường hợp kiểm thử con thứ hai, phương án tối ưu là nối cánh đồng $3$ và $4$ bằng một con đường. Không cần con đường thứ hai.

Nhiệm vụ con

• Bộ kiểm thử 2 thỏa mãn $N \le 20$.
• Các bộ kiểm thử 3-5 thỏa mãn $N \le 10^3$.
• Các bộ kiểm thử 6-10 không có ràng buộc bổ sung.

Tác giả bài toán: Nick Wu