З'єднання двох амбарів
Ферма Джона складається з n полів, пронумерованих послідовно від 1 до n. Між цими полями існує m (0 ≤ m ≤ 10^5) двонаправлених доріжок, які з'єднують пари полів.
На цій фермі розташовані два амбари: один у полі 1, а інший у полі n. Джон хоче переконатися, що існує шлях між цими двома амбарами через послідовність доріжок. Він готовий побудувати до двох нових доріжок, щоб досягти цієї мети. Вартість побудови доріжки між полями i та j визначається як (i − j) ^ 2.
Допоможіть Джону визначити мінімальну вартість, щоб амбари 1 і n стали досяжними один для одного.
Вхідні дані
Перший рядок містить кількість тестів t (1 ≤ t ≤ 20).
Кожен тест починається з двох цілих чисел n (1 ≤ n ≤ 10^5) і m. Кожен з наступних m рядків містить два цілі числа i і j, що вказують на шлях між двома різними полями i і j. Гарантується, що між будь-якими двома полями існує не більше одного шляху, і що сума n + m для всіх тестів не перевищує 5 * 10^5.
Вихідні дані
Виведіть t рядків. i-ий рядок повинен містити одне ціле число - мінімальну вартість для i-го тесту.
Приклад
У першому тесті оптимально з'єднати поля 2 і 3, а також поля 3 і 4.
У другому тесті оптимально з'єднати поля 3 і 4. Другий шлях не потрібен.