Connecting the Barns

Farmer John owns a farm with (N) fields numbered from (1) to (N) ((1 \le N \le 10^5)) and (M) bidirectional roads ((0 \le M \le 10^5)), each connecting two of the fields. There are two barns on the farm: one in field (1) and the other in field (N).

Farmer John wants to ensure that there exists a way to travel between the two barns along a sequence of roads. To achieve this, he is willing to build at most two new roads. The cost of building a road between fields (i) and (j) is given by ( (i - j)^2 ).

Your task is to compute the minimum cost needed to ensure that barn (1) and barn (N) are connected. Note that if the barns are already connected via the existing roads, the cost is (0).

There are two possible ways to connect barn (1) and barn (N):

1. Build one new road directly connecting a field from the component containing barn (1) and a field from the component containing barn (N). The cost for this is ( \min_{i \in C_1, ; j \in C_N} (i - j)^2 ).
   
2. Build two new roads by selecting an intermediate component (X) (different from (C_1) and (C_N)) and connecting it with both barn components. The cost in this case is ( \min_{i \in C_1, ; j \in X} (i - j)^2 + \min_{k \in X, ; l \in C_N} (k - l)^2 ).
   
   You need to output the minimum cost among these possibilities.

inputFormat

The first line contains two integers (N) and (M).

The next (M) lines each contain two integers (u) and (v), indicating that there is a bidirectional road between fields (u) and (v).

outputFormat

Output a single integer, the minimum cost required to ensure that barn (1) and barn (N) are connected.

sample

4 2
1 2
3 4

1