La ferme de Farmer John est constituée de $N$ champs $(1 \leq N \leq 10^5)$, commodément numérotés $1 \ldots N$. Entre ces champs se trouvent $M$ chemins bidirectionnels $(0 \leq M \leq 10^5)$, chacun reliant une paire de champs.

La ferme contient deux étables, l'une dans le champ $1$ et l'autre dans le champ $N$. Farmer John souhaite s'assurer qu'il est possible de marcher entre les deux étables en suivant une succession de chemins. Il est prêt à construire jusqu'à deux nouveaux chemins pour atteindre cet objectif. En raison de la disposition des champs, le coût de construction d'un nouveau chemin entre les champs $i$ et $j$ est $(i-j)^2$.

Aidez Farmer John à déterminer le coût minimal nécessaire pour que les étables $1$ et $N$ deviennent accessibles l'une depuis l'autre.

Entrée

Chaque test d'entrée contient $T$ sous-tests ($1\le T\le 20$), qui doivent tous être résolus correctement pour réussir le test d'entrée.

La première ligne de l'entrée contient $T$, suivi de $T$ sous-tests.

Chaque sous-test commence par deux entiers, $N$ et $M$. Ensuite viennent $M$ lignes, chacune contenant deux entiers $i$ et $j$, indiquant un chemin entre deux champs distincts $i$ et $j$. Il est garanti qu'il existe au plus un chemin entre deux champs quelconques, et que la somme de $N+M$ sur tous les sous-tests est au plus $5 \cdot 10^5$.

Sortie

Affichez $T$ lignes. La $i$-ème ligne doit contenir un unique entier donnant le coût minimal pour le $i$-ème sous-test.

Exemples

Entrée 1

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

Sortie 1

2
1

Remarque

Dans le premier sous-test, il est optimal de relier les champs $2$ et $3$ par un chemin, et les champs $3$ et $4$ par un autre chemin.

Dans le deuxième sous-test, il est optimal de relier les champs $3$ et $4$ par un chemin. Aucun deuxième chemin n'est nécessaire.

Sous-tâches

• Le test 2 vérifie $N \le 20$.
• Les tests 3-5 vérifient $N \le 10^3$.
• Les tests 6-10 n'ont aucune contrainte supplémentaire.

Auteur du problème : Nick Wu