Die Farm von Farmer John besteht aus $N$ Feldern $(1 \leq N \leq 10^5)$, die praktischerweise mit $1 \ldots N$ nummeriert sind. Zwischen diesen Feldern gibt es $M$ Wege, die in beide Richtungen begehbar sind $(0 \leq M \leq 10^5)$ und jeweils zwei Felder verbinden.

Auf der Farm gibt es zwei Scheunen, eine auf Feld $1$ und die andere auf Feld $N$. Farmer John möchte sicherstellen, dass man über eine Folge von Wegen zwischen den beiden Scheunen laufen kann. Um dieses Ziel zu erreichen, ist er bereit, bis zu zwei neue Wege zu bauen. Aufgrund der Lage der Felder betragen die Kosten für einen neuen Weg zwischen den Feldern $i$ und $j$ genau $(i-j)^2$.

Hilf Farmer John, die minimalen Kosten zu bestimmen, mit denen die Scheunen $1$ und $N$ voneinander aus erreichbar werden.

Eingabe

Jeder Eingabetestfall enthält $T$ Untertestfälle ($1\le T\le 20$), die alle korrekt gelöst werden müssen, um den Eingabetestfall zu bestehen.

Die erste Eingabezeile enthält $T$, worauf $T$ Untertestfälle folgen.

Jeder Untertestfall beginnt mit zwei ganzen Zahlen, $N$ und $M$. Danach folgen $M$ Zeilen, die jeweils zwei ganze Zahlen $i$ und $j$ enthalten und einen Weg zwischen zwei verschiedenen Feldern $i$ und $j$ angeben. Es ist garantiert, dass es zwischen je zwei Feldern höchstens einen Weg gibt und dass die Summe von $N+M$ über alle Untertestfälle höchstens $5 \cdot 10^5$ beträgt.

Ausgabe

Gib $T$ Zeilen aus. Die $i$-te Zeile soll eine einzelne ganze Zahl enthalten, die die minimalen Kosten für den $i$-ten Untertestfall angibt.

Beispiele

Eingabe 1

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

Ausgabe 1

2
1

Hinweis

Im ersten Untertestfall ist es optimal, die Felder $2$ und $3$ durch einen Weg und die Felder $3$ und $4$ durch einen weiteren Weg zu verbinden.

Im zweiten Untertestfall ist es optimal, die Felder $3$ und $4$ durch einen Weg zu verbinden. Ein zweiter Weg wird nicht benötigt.

Teilaufgaben

• Testfall 2 erfüllt $N \le 20$.
• Die Testfälle 3-5 erfüllen $N \le 10^3$.
• Für die Testfälle 6-10 gelten keine zusätzlichen Beschränkungen.

Aufgabenautor: Nick Wu