loop do
  roots = Hash.new([])
  i = 0
  loop do
    exit unless (l = $<.gets)
    break if (l = l.split.map(&:to_i)) == [0, 0]
    a, b = l
    roots[a] += [[b, i]]
    roots[b] += [[a, i]]
    i += 1
  end
  
  try = ->(spot, visited) {
    if spot == 2
      return true if visited == 2 ** i - 1
    else
      roots[spot].each do |nxt, root|
        next if (2 ** root & visited).nonzero?
        return true if try.(nxt, 2 ** root | visited)
      end
    end
    false
  }
  puts try.(1, 0) ? "OK" : "NG"
end
