Ферма Джона состоит из множества \(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\) стали достижимы друг для друга.
ФОРМКАТ ВВОДА (с клавиатуры / stdin):
Каждый входной тест содержит
\(T\) под тестов (
\(1\le T\le 20\)), все из которых
должны быть решены правильно, чтобы пройти этот тест.
Первая строка ввода содержит \(T\), за которым следуют \(T\) подтестов.
Каждый подтест начинается с двух целых чисел \(N\) и \(M\). Каждая из последующих
\(M\) строк содержит два целых числа \(i\) и \(j\), означающих путь между двумя различными
полями \(i\) и \(j\). Гарантируется, что имеется не более одного пути между любыми двумя полями.
и что сумма \(N+M\) для всех подтестов не более \(5 \cdot 10^5\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите \(T\) строк. \(i\)-ая строка должна содержать одно целое число, минимальную стоимость
для \(i\)-го подтеста.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
5 2
1 2
4 5
5 3
1 2
2 3
4 5
|
2
1
|