Ферма Джона складається з множини \(N\) полів \((1 \leq N \leq 10^5)\), послідовно пронумерованих \(1 \ldots N\). Між цими полями є \(M\) двонаправлених доріжок \((0 \leq M \leq 10^5)\), що з'єднують пари полів.

На цій фермі є дві ферми - одна у полі \(1\), інша у полі \(N\). ФД хоче бути впевнений, що є шлях між двома фермами послідовністю доріжок. Він готовий побудувати до двох нових доріжок, щоб досягти своєї мети. Вартість побудови доріжки між полями \(i\) та \(j\) є \((i-j)^2\).

Допоможіть ФД визначити мінімальну вартість зробити так, щоб ферми \(1\) і \(N\) стали досяжні одна для одної.

Формат вхідних даних

Кожен вхідний тест містить \(T\) під тестів (\(1\le T\le 20\)), всі з яких повинні бути вирішені правильно, щоб пройти цей тест.

Перший рядок введення містить \(T\), за яким слідують \(T\) підтести.

Кожен підтест починається з двох цілих чисел \(N\) і \(M\). Кожен з наступних \(M\) рядків містить два цілих числа \(i\) і \(j\), що означають шлях між двома різними полями \(i\) та \(j\).

Гарантується, що є не більше одного шляху між двома полями. і що сума \(N+M\) для всіх підтестів не більше \(5 \cdot 10^5\).

Формат вихідних даних

Виведіть \(T\) рядків. \(i\)-ий рядок повинен містити одне ціле число, мінімальну вартість для \(i\)-го підтесту.

Приклад вхідних даних-1

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

Приклад вихідних даних-1

2
1

Пояснення до прикладу

У першому підтесті оптимально з'єднати поля 2 та 3, а також поля 3 та 4.

 У першому підтесті оптимально з'єднати поля 3 та 4. Другий шлях не потрібен.

Оцінювання

У тесті 2 \(N \le 20\).
У тестах 3-5 \(N \le 10^3\).
У тестах 6-10 немає додаткових обмежень.