A quinta de Farmer John consiste num conjunto de $N$ campos $(1 \leq N \leq 10^5)$, convenientemente numerados $1 \ldots N$. Entre estes campos existem $M$ caminhos bidirecionais $(0 \leq M \leq 10^5)$, cada um ligando um par de campos.

A quinta contém dois estábulos, um no campo $1$ e o outro no campo $N$. Farmer John pretende garantir que é possível caminhar entre os dois estábulos ao longo de uma sequência de caminhos. Está disposto a construir até dois caminhos novos para alcançar este objetivo. Devido à disposição dos campos, o custo de construir um caminho novo entre os campos $i$ e $j$ é $(i-j)^2$.

Ajude Farmer John a determinar o custo mínimo necessário para que os estábulos $1$ e $N$ se tornem acessíveis um a partir do outro.

Entrada

Cada caso de teste de entrada contém $T$ subcasos ($1\le T\le 20$), todos os quais devem ser resolvidos corretamente para passar o caso de entrada.

A primeira linha da entrada contém $T$, após a qual se seguem $T$ subcasos de teste.

Cada subcaso de teste começa com dois inteiros, $N$ e $M$. Seguem-se $M$ linhas, cada uma contendo dois inteiros $i$ e $j$, que indicam um caminho entre dois campos diferentes $i$ e $j$. É garantido que existe no máximo um caminho entre quaisquer dois campos e que a soma de $N+M$ sobre todos os subcasos de teste é no máximo $5 \cdot 10^5$.

Saída

Imprima $T$ linhas. A $i$-ésima linha deve conter um único inteiro com o custo mínimo para o $i$-ésimo subcaso de teste.

Exemplos

Entrada 1

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

Saída 1

2
1

Nota

No primeiro subcaso de teste, é ótimo ligar os campos $2$ e $3$ com um caminho e os campos $3$ e $4$ com outro caminho.

No segundo subcaso de teste, é ótimo ligar os campos $3$ e $4$ com um caminho. Não é necessário um segundo caminho.

Subtarefas

• O caso de teste 2 satisfaz $N \le 20$.
• Os casos de teste 3-5 satisfazem $N \le 10^3$.
• Os casos de teste 6-10 não têm restrições adicionais.

Autor do problema: Nick Wu