output_description: If he can achieve the objective, print `OK`; if he cannot, print `NG`.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      K
      A B
attempt: from bisect import bisect_left
  from collections import deque
  import copy
  
  
  def lis(A: list):
      L = [A[0]]
      for a in A[1:]:
          if a > L[-1]:
              # Lの末尾よりaが大きければ増加部分列を延長できる
              L.append(a)
          else:
              # そうでなければ、「aより小さい最大要素の次」をaにする
              # 該当位置は、二分探索で特定できる
              L[bisect_left(L, a)] = a
      return len(L)
  
  
  n = int(input())
  a = tuple(map(int, input().split()))
  G = [[] for _ in range(n + 1)]
  for i in range(n - 1):
      u, v = map(int, input().split())
      G[u].append(v)
      G[v].append(u)
  
  letu = [[] for _ in range(n + 1)]
  letu[1].append(1)
  que = deque([1])
  
  while que:
      q = que.popleft()
  
      for nq in G[q]:
          let = copy.deepcopy(letu[q])
          if letu[nq] != []:  # seen配列としても使う。seenないと閉路でWA
              continue
          let = let + [nq]
          letu[nq] = let
          que.append(nq)
  for j in range(1, n + 1):
      tmp = [a[aa - 1] for aa in letu[j]]
      print(lis(tmp))
  
problem_description: Statement
  
  Takahashi the Jumbo will practice golf.
  
  His objective is to get a carry distance that is a multiple of K, while he can
  only make a carry distance of between A and B (inclusive).
  
  If he can achieve the objective, print `OK`; if he cannot, print `NG`.
samples: [{"input": "7\n    500 600", "output": "OK\n    \n\nAmong the multiples of 7, for example, 567 lies between 500 and 600.\n\n* * *"}, {"input": "4\n    5 7", "output": "NG\n    \n\nNo multiple of 4 lies between 5 and 7.\n\n* * *"}, {"input": "1\n    11 11", "output": "OK"}]