### constant

MAX_INT = 1 << 30

### subroutines

def min_cover(k, bits)
  return 0 if bits == 0
  return MAX_INT if k >= $x

  mc = min_cover(k + 1, bits)

  if (bits & (1 << k)) != 0
    bits &= ~(1 << k)
    $nbrs[k].each{|nk| bits &= ~(1 << nk)}
    mc0 = 1 + min_cover(k + 1, bits)
    mc = mc0 if mc > mc0
  end

  mc
end

### main

loop do
  $x, $y = gets.split.map(&:to_i)
  break if $x == 0 && $y == 0

  $nbrs = $x.times.map{[]}

  $y.times do
    ai, bi = gets.split.map(&:to_i)
    $nbrs[ai] << bi
    $nbrs[bi] << ai
  end
  #p $nbrs

  puts min_cover(0, (1 << $x) - 1)
end