Farma Farmer John składa się z $N$ pól $(1 \leq N \leq 10^5)$, dla wygody ponumerowanych $1 \ldots N$. Między tymi polami istnieje $M$ dwukierunkowych dróg $(0 \leq M \leq 10^5)$, z których każda łączy parę pól.

Na farmie znajdują się dwie stodoły: jedna na polu $1$, a druga na polu $N$. Farmer John chciałby zapewnić możliwość przejścia między dwiema stodołami pewną sekwencją dróg. Aby osiągnąć ten cel, jest gotów zbudować co najwyżej dwie nowe drogi. Ze względu na położenie pól koszt budowy nowej drogi między polami $i$ i $j$ wynosi $(i-j)^2$.

Pomóż Farmer John wyznaczyć minimalny koszt potrzebny do tego, aby stodoły $1$ i $N$ stały się osiągalne jedna z drugiej.

Wejście

Każdy wejściowy przypadek testowy zawiera $T$ podprzypadków ($1\le T\le 20$), które wszystkie trzeba rozwiązać poprawnie, aby zaliczyć wejściowy przypadek testowy.

Pierwszy wiersz wejścia zawiera $T$, po czym następuje $T$ podprzypadków testowych.

Każdy podprzypadek testowy zaczyna się od dwóch liczb całkowitych, $N$ i $M$. Następnie występuje $M$ wierszy, z których każdy zawiera dwie liczby całkowite $i$ i $j$, wskazujące drogę między dwoma różnymi polami $i$ i $j$. Gwarantuje się, że między dowolnymi dwoma polami jest co najwyżej jedna droga oraz że suma $N+M$ po wszystkich podprzypadkach testowych wynosi co najwyżej $5 \cdot 10^5$.

Wyjście

Wypisz $T$ wierszy. W $i$-tym wierszu powinna znajdować się jedna liczba całkowita oznaczająca minimalny koszt dla $i$-tego podprzypadku testowego.

Przykład

Wejście 1

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

Wyjście 1

2
1

Uwagi

W pierwszym podprzypadku testowym optymalnie jest połączyć pola $2$ i $3$ jedną drogą, a pola $3$ i $4$ drugą.

W drugim podprzypadku testowym optymalnie jest połączyć pola $3$ i $4$ jedną drogą. Druga droga nie jest potrzebna.

Podzadania

• Test 2 spełnia $N \le 20$.
• Testy 3-5 spełniają $N \le 10^3$.
• Testy 6-10 nie mają dodatkowych ograniczeń.

Autor zadania: Nick Wu