Ферма Джона состоит из множества 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. Второй путь не требуется.