class Edge
  attr_accessor :dest, :weight
  def initialize dest, weight
    @dest = dest
    @weight = weight
  end
end


class Graph
  def initialize n
    @n = n + 1
    @adjenceList = []
    @n.times do |i|
      @adjenceList[i] = []
    end
  end

  def addEdge i, j, weight
    edge1 = Edge.new j, weight
    @adjenceList[i] << edge1

    edge2 = Edge.new i, weight
    @adjenceList[j] << edge2
  end

  def menboku
    kiten_count = 0
    @n.times do |i|
      is_kiten = @adjenceList[i].length % 2 == 1
      if is_kiten
        kiten_count += 1
      end
    end

    if kiten_count == 0 || kiten_count == 2
      puts "OK"
    else
      puts "NG"
    end
  end

  def printMatrix
    matrix = []
    @n.times do |i|
      matrix[i] = []
      @n.times do |j|
        matrix[i][j] = 0
      end
    end

    @n.times do |i|
      @adjenceList[i].each do |edge|
        matrix[i][edge.dest] = 1
      end
    end

    matrix.each do |row|
      count = 0
      row.each do |i|
        if count == 0
          print i
          count += 1
        else
          print " ", i
        end
      end
      puts ""
    end
  end
end

# graph.printMatrix

data_set = {}
STDIN.each_line {|line|
    n_m = line.split " "
    n = n_m[0].to_i
    n -= 1
    m = n_m[1].to_i
    m -= 1

  if n == -1 && m == -1
      # 出力
      size = data_set.length
      graph = Graph.new size
      data_set.each do | key , val |
        val.each do |vertex|
          graph.addEdge key, vertex, 0
        end
      end
      graph.menboku
      data_set.clear
  else
      if !data_set.has_key? n
        data_set[n] = []
      end
      data_set[n] << m
  end

  coin_str = line
}

