La granja del Granjero Juan consiste en un conjunto de ~N~ campos ~(1 \leq N \leq 10^5)~, numerados convenientemente ~1...N~. Entre esos campos hay ~M~ caminos bi-direccionales ~(0 \leq M \leq 10^5)~, cada uno de los cuales conecta un par de campos.

La granja contiene dos establos, uno en el campo ~1~ y otro en el campo ~N~. Al Granjero Juan le gustaría asegurarse que hay una manera de ir entre los dos establos a lo largo de alguna serie de caminos. El está dispuesto a construir hasta dos caminos nuevos para obtener su propósito. Debido a la manera en que están situados los campos, el costo de construir un camino nuevo entre los campos ~i~ y ~j~ es ~(i-j)^2~.

Por favor ayude al Granjero Juan a determinar el costo mínimo necesario de tal forma que se pueda ir de los establos ~1~ y ~N~ del uno al otro.

Entrada

Cada caso de prueba contiene T subtareas ~(1 \leq T \leq 20)~, todas las cuales deben ser resueltas correctamente para resolver el caso de prueba.

La primera línea de la entrada contiene ~T~, después siguen ~T~ subtareas. Cada subtarea comienza con dos enteros, ~N~ y ~M~. A continuación siguen ~M~ líneas, cada una conteniendo dos enteros i y j, indicando que hay un camino entre dos campos diferentes ~i~ y ~j~. Se garantiza que hay a lo más un camino entre dos campos, y que la suma de ~N+M~ sobre todas las subtareas es a lo más ~5 \cdot 10^5~.

Salida

Dé como salida ~T~ líneas. La línea i-ésima debe contener un solo entero dando el costo mínimo para la subtarea i-ésima.

Ejemplo de Entrada

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

Ejemplo de Salida

2
1

En la primera subtarea, es óptimo conectar a los campos 2 y 3 con un camino y a los campos 3 y 4 con un camino. En la segunda subtarea, es óptimo conectar a los campos 3 y 4 con un camino. No se necesita un segundo camino.

USACO 2021 December Contest, Silver Problem 2. Connecting Two Barns.