require 'set'
n, m = gets.split.map(&:to_i)
g = (0..n).map { Set.new }
m.times do
  i, j = gets.split.map(&:to_i)
  g[i] << j
  g[j] << i
end

queue = [1 << 1]
dist = { 1 << 1 => 0 }
until queue.empty?
  x = queue.shift
  d = dist[x]
  g[x >> 1].each do |j|
    y = (j << 1) + (1 - d % 2)
    next if dist[y]
    dist[y] = d + 1
    queue << y
  end
end

if dist.size == 2 * n
  p [
    dist.select {|x, _| x.even? }.map(&:last).max,
    dist.select {|x, _| x.odd? }.map(&:last).max
  ].min
else
  p -1
end
