class Node attr_accessor :parent, :rank def initialize(n) @parent = n @rank = 0 end end class UnionFindTree def initialize(n) @nodes = (0..n).to_a.map { |i| Node.new(i) } end def find(x) return @nodes[x].parent == x ? x : @nodes[x].parent = find(@nodes[x].parent) end def unite(a, b) a = find(a) b = find(b) return if a == b if @nodes[a].rank < @nodes[b].rank @nodes[a].parent = b else @nodes[b].parent = a @nodes[a].rank += 1 if @nodes[a].rank == @nodes[b].rank end end def same?(a, b) find(a) == find(b) end # 確認用。アルゴリズムとは関係無い def parents @nodes.map(&:parent) end end n = gets.to_i # n, q = gets.split.map(&:to_i) uft = UnionFindTree.new(n) (n-1).times do |i| x,y = gets.split.map(&:to_i) # if com == 0 uft.unite(x, y) # else # puts uft.same?(x, y) ? 1 : 0 # end end n.times do |i| (0...i).each do |j| if not uft.same?(i,j) puts "Alice" exit # flag = false # break end end end puts "Bob"