n,m = gets.split.map(&:to_i) x = n.times.map{[]} at = 0 m.times{ a,b=gets.split.map(&:to_i) at=a x[a] << b x[b] << a } uni = 0 odd = 0 x.each{|t| s = t.size uni += 1 if s>0 odd += 1 if s%2==1 } con = 0 q = [at] ch = Array.new(n, false) while q.size>0 now = q.pop ch[now] = true x[now].each{|ne| next if ch[ne] q<