Vova and Marina love offering puzzles to each other. Today Marina offered Vova to cope with the following task.

Vova has a non-directed graph consisting of n vertices and m edges without loops and multiple edges. Let's define the operation of contraction two vertices a and b that are not connected by an edge. As a result of this operation vertices a and b are deleted and instead of them a new vertex x is added into the graph, and also edges are drawn from it to all vertices that were connected with a or with b (specifically, if the vertex was connected with both a and b, then also exactly one edge is added from x to it). Thus, as a result of contraction again a non-directed graph is formed, it contains no loops nor multiple edges, and it contains (n - 1) vertices.

Vova must perform the contraction an arbitrary number of times to transform the given graph into a chain of the maximum length. A chain of length k (k ≥ 0) is a connected graph whose vertices can be numbered with integers from 1 to k + 1 so that the edges of the graph connect all pairs of vertices (i, i + 1) (1 ≤ i ≤ k) and only them. Specifically, the graph that consists of one vertex is a chain of length 0. The vertices that are formed as a result of the contraction are allowed to be used in the following operations of contraction.

 [Image] The picture illustrates the contraction of two vertices marked by red. 

Help Vova cope with his girlfriend's task. Find the maximum length of the chain that can be obtained from the resulting graph or else determine that it is impossible to obtain the chain.


-----Input-----

The first line contains two integers n, m (1 ≤ n ≤ 1000, 0 ≤ m ≤ 100 000) — the number of vertices and the number of edges in the original graph.

Next m lines contain the descriptions of edges in the format a_{i}, b_{i} (1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i}), which means that there is an edge between vertices a_{i} and b_{i}. It is guaranteed that there is at most one edge between each pair of vertexes.


-----Output-----

If it is impossible to obtain a chain from the given graph, print  - 1. Otherwise, print the maximum possible number of edges in the resulting chain.


-----Examples-----
Input
5 4
1 2
2 3
3 4
3 5

Output
3

Input
4 6
1 2
2 3
1 3
3 4
2 4
1 4

Output
-1

Input
4 2
1 3
2 4

Output
2



-----Note-----

In the first sample test you can contract vertices 4 and 5 and obtain a chain of length 3.

In the second sample test it is initially impossible to contract any pair of vertexes, so it is impossible to achieve the desired result.

In the third sample test you can contract vertices 1 and 2 and obtain a chain of length 2.

Difficulty: VERY_HARD
Tags: Graph algorithms

Shortest paths

Starter code:

Solutions:
def solve():
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	global maxValue
	maxValue = n * 2
	graph = [[] for _ in range(0, n)]
	edges = []
	diameters = []
	for _ in range(0, m):
		(u, v) = input().split()
		u = int(u) - 1
		v = int(v) - 1
		edges.append(v)
		graph[u].append(v)
		graph[v].append(u)
	distance = [maxValue] * n
	queueCc = [0] * n
	queue = [0] * n
	for i in range(0, n):
		if distance[i] == maxValue:
			qlen = bfs_2k(graph, i, distance, queueCc)
			if qlen == None:
				print(-1)
				return
			diameters.append(distance[queueCc[qlen - 1]] if qlen > 0 else 0)
			for v in range(1, qlen):
				newDistance = [maxValue] * n
				bfs_2k(graph, queueCc[v], newDistance, queue)
				diameters[-1] = max(diameters[-1], newDistance[queue[qlen - 1]])
	print(sum(diameters))

def bfs_2k(graph, initVertex, dist, queue):
	dist[initVertex] = 0
	queue[0] = initVertex
	qlen = qcount = 1
	i = 0
	while qcount:
		u = queue[i]
		qcount -= 1
		i += 1
		for v in graph[u]:
			if dist[v] == maxValue:
				dist[v] = dist[u] + 1
				queue[qlen] = v
				qlen += 1
				qcount += 1
			if (dist[u] - dist[v]) % 2 == 0:
				return None
	return qlen
solve()


from collections import deque

def solve():
	global n, m
	(n, m) = map(lambda x: int(x), input().split())
	global maxVal
	maxVal = n ** 2
	graph = [[] for _ in range(0, n)]
	for _ in range(0, m):
		(u, v) = map(lambda x: int(x) - 1, input().split())
		graph[u].append(v)
		graph[v].append(u)
	ccNum = 0
	cc = [0] * n
	innrCc = [0] * n
	dmtrs = [0] * n
	distance = [maxVal] * n
	for i in range(0, n):
		if distance[i] == maxVal:
			ccLen = bfs_2k(graph, i, distance, cc)
			if ccLen is None:
				print(-1)
				return
			dmtrs[ccNum] = distance[cc[ccLen - 1]]
			for v in range(0, ccLen):
				innrDst = [maxVal] * n
				bfs_2k(graph, cc[v], innrDst, innrCc)
				dmtrs[ccNum] = max(dmtrs[ccNum], innrDst[innrCc[ccLen - 1]])
			ccNum += 1
	print(sum(dmtrs))

def bfs_2k(graph, s, dist, cc):
	queue = deque()
	queue.append(s)
	dist[s] = 0
	ccLen = 0
	while queue:
		u = queue.popleft()
		for v in graph[u]:
			if dist[v] == maxVal:
				dist[v] = dist[u] + 1
				queue.append(v)
				cc[ccLen] = v
				ccLen += 1
			elif (dist[u] - dist[v]) % 2 == 0:
				return None
	return ccLen
solve()


(n, m) = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(m):
	(p, q) = map(int, input().split())
	g[p - 1].append(q - 1)
	g[q - 1].append(p - 1)
comp = [-1] * n

def shortest(root):
	dist = [-1] * n
	q = [0] * n
	(left, right) = (0, 1)
	q[left] = root
	dist[root] = 0
	good = True
	while left < right:
		x = q[left]
		left = left + 1
		for i in g[x]:
			if dist[i] is -1:
				dist[i] = 1 + dist[x]
				q[right] = i
				right = right + 1
			elif dist[i] == dist[x]:
				good = False
	far = 0
	for i in dist:
		if i > far:
			far = i
	return (good, far, dist)
arr = [0] * n
good = True
for i in range(n):
	(_, opt, dist) = shortest(i)
	if _ is False:
		good = False
	if comp[i] is -1:
		for j in range(n):
			if dist[j] is not -1:
				comp[j] = i
	if arr[comp[i]] < opt:
		arr[comp[i]] = opt
if good is False:
	print('-1')
else:
	print(sum(arr))


from collections import deque

def solve():
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	global maxValue
	maxValue = n * 2
	graph = [[] for _ in range(0, n)]
	edges = []
	diameters = []
	for _ in range(0, m):
		(u, v) = input().split()
		u = int(u) - 1
		v = int(v) - 1
		edges.append(v)
		graph[u].append(v)
		graph[v].append(u)
	distance = [maxValue] * n
	cc = [maxValue] * n
	for i in range(0, n):
		if distance[i] == maxValue:
			cc = bfs_2k(graph, i, distance)
			if cc == None:
				print(-1)
				return
			diameters.append(distance[cc[-1]])
			for v in range(1, len(cc)):
				newDistance = [maxValue] * n
				samecc = bfs_2k(graph, cc[v], newDistance)
				diameters[-1] = max(diameters[-1], newDistance[samecc[-1]])
	print(sum(diameters))

def bfs_2k(graph, initVertex, dist):
	queue = []
	qlen = 1
	queue.append(initVertex)
	dist[initVertex] = 0
	u = None
	i = 0
	while qlen:
		u = queue[i]
		qlen -= 1
		for v in graph[u]:
			if dist[v] == maxValue:
				dist[v] = dist[u] + 1
				queue.append(v)
				qlen += 1
			if (dist[u] - dist[v]) % 2 == 0:
				return None
		i += 1
	return queue
solve()


from collections import deque

def solve():
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	global maxValue
	maxValue = n * 2
	graph = [[] for _ in range(0, n)]
	for _ in range(0, m):
		(u, v) = input().split()
		u = int(u) - 1
		v = int(v) - 1
		graph[u].append(v)
		graph[v].append(u)
	diameters = []
	distance = [maxValue] * n
	cc = [0] * n
	innerCc = [0] * n
	for i in range(0, n):
		if distance[i] == maxValue:
			ccLen = bfs_2k(graph, i, distance, cc)
			if ccLen == None:
				print(-1)
				return
			diameters.append(distance[cc[ccLen - 1]] if ccLen > 0 else 0)
			for v in range(0, ccLen):
				innerDist = [maxValue] * n
				bfs_2k(graph, cc[v], innerDist, innerCc)
				diameters[-1] = max(diameters[-1], innerDist[innerCc[ccLen - 1]])
	print(sum(diameters))

def bfs_2k(graph, initVertex, dist, cc):
	queue = deque()
	queue.append(initVertex)
	dist[initVertex] = 0
	ccLen = 0
	while queue:
		u = queue.popleft()
		for v in graph[u]:
			if dist[v] == maxValue:
				dist[v] = dist[u] + 1
				queue.append(v)
				cc[ccLen] = v
				ccLen += 1
			if (dist[u] - dist[v]) % 2 == 0:
				return None
	return ccLen
solve()