두 헛간 연결하기

Farmer John의 농장은 $N$개의 밭으로 이루어져 있고 $(1 \leq N \leq 10^5)$, 밭에는 $1 \ldots N$의 번호가 붙어 있다. 밭 사이에는 $M$개의 양방향 길이 있고 $(0 \leq M \leq 10^5)$, 각 길은 두 밭을 연결한다.

농장에는 헛간이 두 개 있는데, 하나는 1번 밭에, 다른 하나는 $N$번 밭에 있다. Farmer John은 두 헛간 사이를 길을 따라 걸어서 오갈 수 있게 만들려고 한다. 이를 위해 최대 두 개의 새 길을 지을 수 있다. 밭의 배치 때문에 밭 $i$와 밭 $j$ 사이에 새 길을 지을 때 드는 비용은 $(i-j)^2$이다.

헛간 1과 $N$이 서로 오갈 수 있게 만드는 데 필요한 최소 비용을 구하시오.

각 입력 테스트 케이스는 $T$개의 부분 케이스로 이루어져 있으며 $(1\le T\le 20)$, 입력 케이스를 풀려면 모든 부분 케이스를 올바르게 풀어야 한다.

입력의 첫 줄에는 $T$가 주어지고, 그 뒤에 $T$개의 부분 테스트 케이스가 이어진다.

각 부분 테스트 케이스는 두 정수 $N$과 $M$으로 시작한다. 다음 $M$개의 줄에는 각각 두 정수 $i$와 $j$가 주어지며, 이는 서로 다른 두 밭 $i$와 $j$ 사이의 길을 나타낸다. 임의의 두 밭 사이에 길이 최대 하나만 존재하며, 모든 부분 테스트 케이스에 대한 $N+M$의 합은 $5 \cdot 10^5$ 이하이다.

$T$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 부분 테스트 케이스의 최소 비용을 나타내는 정수 하나를 출력한다.