You are given a graph with N vertices (numbered 1 to N) and M bidirectional edges, which doesn't contain multiple edges or self-loops — that is, the given graph is a simple undirected graph.

For each pair of vertices a, b such that 1 ≤ a, b ≤ N, it is possible to add a new edge between vertices a and b to the graph, with a cost of (a - b)^2.

Find the minimum cost of adding edges so that vertex N is reachable from vertex 1.

------ Input Format ------ 

- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains 2 space-separated integers, N and M.
- The i^{th} of the next M lines contains 2 space-separated integers u_{i} and v_{i}, denoting a bidirectional edge between vertex u_{i} and vertex v_{i} in the graph.

------ Output Format ------ 

For each test case, output the answer in a single line.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$2 ≤ N ≤ 2 \cdot 10^{5}$
$0 ≤ M ≤ 2 \cdot 10^{5}$
$1 ≤ u_{i}, v_{i} ≤ N$
- The graph doesn't contain self-loops or multiple edges
- Sum of $N$ over all testcases is no more than $2 \cdot 10^{5}$.
- Sum of $M$ over all testcases is no more than $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
2 0
5 4
3 2
1 4
5 3
4 2
6 3
1 2
3 2
1 3

----- Sample Output 1 ------ 
1
0
3

----- explanation 1 ------ 
Test Case $1$: Add an edge between vertices $1$ and $2$, with cost $(1-2)^2 = 1$.

Test Case $2$: Vertices $1$ and $5$ are already connected, so no edges need to be added.

Difficulty: HARD
Tags: Graph algorithms

Shortest paths

Starter code:

Solutions:
import heapq

def find_min_cost(City, Road, adj):
	cost = [float('inf') for i in range(City + 1)]
	cost[1] = 0
	flag = [False for i in range(City + 1)]
	start = [[0, 1]]
	while len(start):
		(_, p) = heapq.heappop(start)
		if flag[p]:
			continue
		flag[p] = True
		for e in adj[p]:
			if cost[e[0]] > cost[p] + e[1]:
				cost[e[0]] = cost[p] + e[1]
				heapq.heappush(start, [cost[e[0]], e[0]])
	return cost[City]
t = int(input())
for _ in range(t):
	line = input().split()
	(c, r) = (int(line[0]), int(line[1]))
	adj = [[] for i in range(c + 1)]
	for _ in range(r):
		edge = input().split()
		(p, q) = (int(edge[0]), int(edge[1]))
		adj[p].append([q, 0])
		adj[q].append([p, 0])
	for i in range(1, c):
		adj[i].append([i + 1, 1])
		adj[i + 1].append([i, 1])
	print(find_min_cost(c, r, adj))


import heapq

def dijkstra():
	dist = [float('inf') for i in range(n + 1)]
	dist[1] = 0
	visited = set()
	q = []
	heapq.heapify(q)
	heapq.heappush(q, [0, 1])
	while len(q):
		(dis, u) = heapq.heappop(q)
		if u in visited:
			continue
		visited.add(u)
		for (v, w_uv) in ad[u]:
			if dist[v] > dist[u] + w_uv:
				dist[v] = dist[u] + w_uv
				heapq.heappush(q, [dist[v], v])
	return dist[n]
t = int(input())
while t:
	inp = input().split()
	n = int(inp[0])
	m = int(inp[1])
	e = set()
	ad = [[] for i in range(n + 1)]
	for i in range(m):
		inpt = input().split()
		u = int(inpt[0])
		v = int(inpt[1])
		e.add((u, v))
		e.add((v, u))
		ad[u].append([v, 0])
		ad[v].append([u, 0])
	for i in range(1, n):
		if (i, i + 1) not in e:
			ad[i].append([i + 1, 1])
			ad[i + 1].append([i, 1])
	print(dijkstra())
	t -= 1


from heapq import heappop, heappush
for op in range(int(input())):
	(n, m) = map(int, input().split())
	gr = [set() for _ in range(n)]
	for _ in range(m):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		gr[a].add(b)
		gr[b].add(a)
	q = [0]
	seen = set()
	while q:
		node = q.pop()
		seen.add(node)
		for nie in gr[node]:
			if nie not in seen:
				q.append(nie)
	q = [(0, n - 1)]
	p = {}
	while q:
		(cost, node) = heappop(q)
		if node in seen:
			print(cost)
			break
		for nie in gr[node]:
			if nie not in p or p[nie] > cost:
				heappush(q, (cost, nie))
				p[nie] = cost
		nie = node - 1
		if nie not in gr[node]:
			if nie not in p or p[nie] > cost + 1:
				heappush(q, (cost + 1, nie))
				p[nie] = cost + 1
		nie = node + 1
		if nie < n:
			if nie not in gr[node]:
				if nie not in p or p[nie] > cost + 1:
					heappush(q, (cost + 1, nie))
					p[nie] = cost + 1


import heapq

def dijktra(graph, h):
	explored = ['n' for i in range(graph.v_count)]
	while explored[-1] == 'n':
		(val, vertex) = heapq.heappop(h)
		if explored[vertex - 1] == 'n':
			for neigh in graph.vertices[vertex]:
				if explored[neigh - 1] == 'n':
					(v1, v2) = sorted([neigh, vertex])
					temp = val + graph.edges[v1, v2]
					heapq.heappush(h, (temp, neigh))
		explored[vertex - 1] = 'y'
	return val

class Graph:

	def __init__(self, v, e):
		self.edges = {}
		self.vertices = {}
		self.v_count = v
		self.e_count = e
for t in range(int(input())):
	(v, e) = map(int, input().split(' '))
	graph = Graph(v, e)
	h = []
	for j in range(e):
		(v1, v2) = map(int, input().split(' '))
		graph.edges[tuple(sorted([v1, v2]))] = 0
		if v1 not in graph.vertices:
			graph.vertices[v1] = []
		if v2 not in graph.vertices:
			graph.vertices[v2] = []
		graph.vertices[v1].append(v2)
		graph.vertices[v2].append(v1)
	for j in range(1, v):
		if (j, j + 1) not in graph.edges:
			graph.edges[j, j + 1] = 1
			(v1, v2) = (j, j + 1)
			if v1 not in graph.vertices:
				graph.vertices[v1] = []
			if v2 not in graph.vertices:
				graph.vertices[v2] = []
			graph.vertices[v1].append(v2)
			graph.vertices[v2].append(v1)
	heapq.heappush(h, (0, 1))
	print(dijktra(graph, h))


import sys
sys.setrecursionlimit(10 ** 6)
from heapq import heappush, heappop
from sys import maxsize as inf

def dijkstra(graph, n, src):
	vis = [False] * n
	heap = []
	dist = [inf] * n
	dist[src] = 0
	vis[src] = True
	heappush(heap, (0, src))
	while heap:
		(d, node) = heappop(heap)
		if dist[node] < d:
			continue
		vis[node] = True
		for (adj, weight) in graph[node]:
			if not vis[adj] and d + weight < dist[adj]:
				dist[adj] = d + weight
				heappush(heap, (dist[adj], adj))
	return dist[n - 1]
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	adj = [[] for _ in range(n)]
	arr = [False for _ in range(n)]
	for _ in range(m):
		(u, v) = map(int, input().split())
		adj[u - 1].append((v - 1, 0))
		adj[v - 1].append((u - 1, 0))
		if abs(u - v) == 1:
			arr[min(u, v) - 1] = True
	for i in range(n - 1):
		if arr[i]:
			continue
		adj[i].append((i + 1, 1))
		adj[i + 1].append((i, 1))
	print(dijkstra(adj, n, 0))


import sys
from math import sqrt, gcd, factorial
from collections import deque, Counter, OrderedDict
sys.setrecursionlimit(10 ** 6)
input = lambda : sys.stdin.readline()
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(int, input().strip().split()))
mod = 1000000007

def dfs(node, dist):
	v[node] = 1
	cc.append(node)
	d[node] = dist
	for i in adj[node]:
		if not v[i]:
			dfs(i, dist)
for _ in range(I()):
	(n, m) = M()
	adj = {i + 1: [] for i in range(n)}
	for i in range(m):
		(a, b) = M()
		adj[a].append(b)
		adj[b].append(a)
	cc = deque()
	v = [0] * (n + 1)
	d = [0] * (n + 1)
	dfs(n, 0)
	while cc:
		curr = cc.popleft()
		if curr > 1 and (not v[curr - 1]):
			dfs(curr - 1, d[curr] + 1)
		if curr < n and (not v[curr + 1]):
			dfs(curr + 1, d[curr] + 1)
	print(d[1])


from heapq import *
import sys
input = sys.stdin.readline
INF = 10 ** 9
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	edges = set()
	adj = [[] for _ in range(n + 1)]
	for _ in range(m):
		(a, b) = map(int, input().split())
		adj[a].append([b, 0])
		adj[b].append([a, 0])
		edges.add((a, b))
		edges.add((b, a))
	for i in range(1, n):
		if (i, i + 1) not in edges:
			adj[i].append([i + 1, 1])
			adj[i + 1].append([i, 1])
	dis = [INF] * (n + 1)
	dis[1] = 0
	pq = []
	heappush(pq, [0, 1])
	while pq:
		(cur_dis, cur_nd) = heappop(pq)
		for (nex, nex_dis) in adj[cur_nd]:
			if dis[nex] > cur_dis + nex_dis:
				dis[nex] = cur_dis + nex_dis
				heappush(pq, [dis[nex], nex])
	print(dis[n])


from sys import stdin
inp = stdin.readline

def solve_path(N, M):
	nbr = [[] for _ in range(N + 1)]
	avl = [False] + [True] * N
	for _ in range(M):
		(u, v) = map(int, inp().split())
		nbr[u].append(v)
		nbr[v].append(u)
	front = [1]
	avl[1] = False
	cost = 0
	while avl[N]:
		fx = 0
		while fx < len(front):
			for nb in nbr[front[fx]]:
				if avl[nb]:
					front.append(nb)
					avl[nb] = False
			fx += 1
		if not avl[N]:
			break
		fwd = []
		cost += 1
		for f in front:
			for fn in range(f - 1, f + 2, 2):
				if avl[fn]:
					fwd.append(fn)
					avl[fn] = False
		front = fwd
	return cost
T = int(inp())
for tx in range(T):
	(N, M) = map(int, inp().split())
	print(solve_path(N, M))


from collections import defaultdict
import heapq
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	graph = defaultdict(list)
	present = [0 for _ in range(N)]
	for i in range(M):
		(u, v) = map(int, input().split())
		graph[u].append((v, 0))
		graph[v].append((u, 0))
		if abs(u - v) == 1:
			present[min(u, v)] = 1
	for i in range(1, N):
		if present[i] == 0:
			graph[i].append((i + 1, 1))
			graph[i + 1].append((i, 1))
	cost = [float('inf') for _ in range(N + 1)]
	heap = [(0, 1)]
	cost[1] = 0
	while heap:
		(cur_cost, node) = heapq.heappop(heap)
		for (n, c) in graph[node]:
			if c + cur_cost < cost[n]:
				cost[n] = c + cur_cost
				heapq.heappush(heap, (cost[n], n))
	print(cost[-1])


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random
from functools import lru_cache
from itertools import *

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for __ in range(how_much_noob_I_am):
		(n, m) = sep()
		d = defaultdict(list)
		for _ in range(m):
			(a, b) = sep()
			d[a].append(b)
			d[b].append(a)
		q = []
		heapq.heappush(q, [0, 1])
		visited = [False] * (n + 1)
		dis = [inf] * (n + 1)
		dis[1] = 0
		while q:
			(dist, s) = heapq.heappop(q)
			for i in d[s]:
				if dis[i] > dist:
					dis[i] = dist
					heapq.heappush(q, [dist, i])
			if s + 1 <= n:
				if dis[s + 1] > dist + 1:
					dis[s + 1] = dist + 1
					heapq.heappush(q, [dist + 1, s + 1])
			if s - 1 >= 1:
				if dis[s - 1] > dist + 1:
					dis[s - 1] = dist + 1
					heapq.heappush(q, [dist + 1, s - 1])
		print(dis[n])
main()


import sys
RW = lambda : [int(x) for x in sys.stdin.readline().strip().split()]
RI = lambda : int(sys.stdin.readline().strip())
RS = lambda : sys.stdin.readline().strip().split()
from collections import OrderedDict as of
from collections import defaultdict as df
import heapq
import math
from math import ceil, floor
sys.setrecursionlimit(100005)

class Graph:

	def __init__(self, adj):
		self.adj = adj
		self.n = len(self.adj)
		self.vis = [0] * n
		self.minheap = []
		self.dis = [float('inf')] * self.n

	def solve(self):
		self.dis[0] = 0
		self.minheap.append((0, 0))
		while len(self.minheap) > 0:
			(distance, node) = heapq.heappop(self.minheap)
			if self.vis[node] == 1:
				continue
			self.vis[node] = 1
			for (next, nextdis) in self.adj[node]:
				if self.vis[next] == 1:
					continue
				disttemp = distance + nextdis
				if disttemp < self.dis[next]:
					self.dis[next] = disttemp
					heapq.heappush(self.minheap, (disttemp, next))
t = RI()
for _ in range(t):
	(n, m) = RW()
	adj = [[] for i in range(n)]
	for i in range(m):
		(a, b) = RW()
		a -= 1
		b -= 1
		adj[a].append((b, 0))
		adj[b].append((a, 0))
	for i in range(n - 1):
		adj[i].append((i + 1, 1))
		adj[i + 1].append((i, 1))
	g = Graph(adj)
	g.solve()
	print(g.dis[n - 1])


from collections import defaultdict
import heapq
import math
from math import sqrt
for _ in range(int(input())):
	g = defaultdict(dict)
	d = defaultdict(dict)
	(n, q) = map(int, input().split())
	for i in range(1, n):
		g[i][i + 1] = 1
		g[i + 1][i] = 1
	for i in range(q):
		(m, k) = map(int, input().split())
		g[m][k] = 0
		g[k][m] = 0
	global ans
	ans = 0

	def dij():
		h = [(0, 1)]
		p = [float('inf') for i in range(n + 1)]
		p[1] = 0
		global ans
		while h:
			(x, y) = heapq.heappop(h)
			if y == n:
				ans = x
				break
			v[y] = True
			for j in g[y]:
				if v[j]:
					continue
				d = x + g[y][j]
				if d < p[j]:
					p[j] = d
					heapq.heappush(h, (d, j))
	v = [False for i in range(n + 1)]
	dij()
	print(ans)


import math, bisect, heapq, random, sys, itertools
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
ints = lambda : list(map(int, input().split()))
alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
p2 = [1]
for i in range(70):
	p2.append(p2[-1] * 2)
p = 10 ** 9 + 7
ANS = []
graph = []
visited = []

def bfs(queue, n, x):
	done = set()
	while queue:
		q = set()
		for i in queue:
			done.add(i)
			for j in graph[i]:
				if visited[j] == -1:
					visited[j] = x
					q.add(j)
		queue = q
	next_q = set()
	for i in done:
		if i - 1 >= 1 and visited[i - 1] == -1:
			visited[i - 1] = x + 1
			next_q.add(i - 1)
		if i + 1 <= n and visited[i + 1] == -1:
			visited[i + 1] = x + 1
			next_q.add(i + 1)
	if next_q:
		bfs(next_q, n, x + 1)
for t in range(int(input())):
	(n, m) = ints()
	graph = [set() for i in range(n + 1)]
	visited = [-1] * (n + 1)
	for i in range(m):
		(x, y) = ints()
		graph[x].add(y)
		graph[y].add(x)
	visited[1] = 0
	bfs([1], n, 0)
	print(visited[n])


from heapq import *
from dis import dis
import os.path
from math import gcd, floor, ceil
from collections import *
from random import randint
import re
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	(n, m) = mp()
	d = defaultdict(list)
	x = [0] * (n + 1)
	for i in range(m):
		(a, b) = mp()
		(a, b) = (min(a, b), max(a, b))
		d[a].append((b, 0))
		d[b].append((a, 0))
		if b - a == 1:
			x[a] = 1
	for i in range(1, n):
		if x[i] == 0:
			d[i].append((i + 1, 1))
			d[i + 1].append((i, 1))
	h = [(0, 1)]
	v = [0] * (n + 1)
	dist = [INF] * (n + 1)
	dist[1] = 0
	while h:
		(b, a) = heappop(h)
		if v[a]:
			continue
		v[a] = 1
		for i in d[a]:
			if b + i[1] < dist[i[0]]:
				dist[i[0]] = b + i[1]
				heappush(h, (dist[i[0]], i[0]))
	pr(dist[n])
for _ in range(inp()):
	solve()


import os.path
from math import gcd, floor, ceil
from collections import *
from random import randint
import re
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():

	def find(a):
		x = []
		while a != par[a]:
			x.append(a)
			a = par[a]
		for i in x:
			par[i] = a
		return a

	def union(a, b):
		a = find(a)
		b = find(b)
		if a != b:
			par[a] = b
	(n, m) = mp()
	par = {i: i for i in range(1, n + 1)}
	for i in range(m):
		(a, b) = mp()
		union(a, b)
	x = defaultdict(list)
	for i in range(1, n + 1):
		x[find(i)].append(i)
	cur = [0] * (n + 1)
	c = 1
	for i in x:
		for j in x[i]:
			cur[j] = c
		c += 1
	d = defaultdict(list)
	for i in range(1, n):
		d[cur[i]].append(cur[i + 1])
		d[cur[i + 1]].append(cur[i])
	dist = [INF] * (c + 1)
	dist[1] = 0
	q = deque()
	q.append(1)
	while q:
		a = q.popleft()
		for i in d[a]:
			if dist[i] == INF:
				q.append(i)
				dist[i] = dist[a] + 1
	pr(dist[cur[n]])
for _ in range(inp()):
	solve()


from sys import stdin
input = stdin.readline
import heapq

def answer():
	ans = [float('inf') for i in range(n + 1)]
	ans[1] = 0
	v = [False for i in range(n + 1)]
	q = [[0, 1]]
	while len(q):
		(val, p) = heapq.heappop(q)
		if v[p]:
			continue
		v[p] = True
		for x in edges[p]:
			if ans[x[0]] > ans[p] + x[1]:
				ans[x[0]] = ans[p] + x[1]
				heapq.heappush(q, [ans[x[0]], x[0]])
	return ans[n]
for T in range(int(input())):
	(n, m) = map(int, input().split())
	edges = [[] for i in range(n + 1)]
	for i in range(m):
		(u, v) = map(int, input().split())
		edges[u].append([v, 0])
		edges[v].append([u, 0])
	for i in range(1, n):
		edges[i].append([i + 1, 1])
		edges[i + 1].append([i, 1])
	print(answer())


import sys
import math
from collections import defaultdict
import heapq

class DisjointSet:

	def __init__(self, n):
		self.parent = []
		for i in range(n):
			self.parent.append(i)

	def find(self, node):
		if node != self.parent[node]:
			self.parent[node] = self.find(self.parent[node])
		return self.parent[node]

	def union(self, u, v):
		leader_u = self.find(u)
		leader_v = self.find(v)
		if leader_v != leader_u:
			self.parent[leader_u] = leader_v

class Graph:

	def __init__(self):
		self.neighbours = defaultdict(list)

	def addEdge(self, u, v, cost):
		self.neighbours[u].append([v, cost])
		self.neighbours[v].append([u, cost])

	def dijkstra(self, source, n):
		distance = defaultdict(lambda : float('inf'))
		visited = defaultdict(lambda : False)
		distance[source] = 0
		pq = [[0, source, 0]]
		heapq.heapify(pq)
		shortest_path_tree = defaultdict(lambda : float('inf'))
		shortest_path_tree[0] = 0
		while pq:
			(d, u, lastAdded) = heapq.heappop(pq)
			for (v, c) in self.neighbours[u]:
				if distance[v] > d + c:
					distance[v] = d + c
					shortest_path_tree[v] = c
					heapq.heappush(pq, [distance[v], v, c])
				if distance[v] == d + c:
					if c < shortest_path_tree[v]:
						distance[v] = d + c
						shortest_path_tree[v] = c
						heapq.heappush(pq, [distance[v], v, c])
		return distance
for some_random_name in range(int(input())):
	(n, m) = map(int, input().split())
	d = {}
	for i in range(n - 1):
		d[i + 1, i + 2] = 1
	for i in range(m):
		(x, y) = map(int, input().split())
		d[x, y] = 0
	g = Graph()
	for i in d:
		g.addEdge(i[0], i[1], d[i])
	distance = g.dijkstra(1, n)
	print(distance[n])