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 x[now].each{|ne| next if ch[ne] q << ne ch[ne] = true } con+=1 end if con