In 1862, the lord of Aizu was ordered to serve as a guardian of Kyoto. The Kyoto Shugoshoku is an important role to protect Kyoto at the end of the Edo period when security has deteriorated. You have to patrol the city by sharing it with the shogunate and other clan. However, when it came time to decide the sharing route, the following order was received from a stubborn old man who is famous among his vassals.

<image>


It was a big deal. Even the lord cannot ignore the statement of this vassal. Depending on the selection of the sharing route, it will be "the samurai's face is not noticeable".

So, please make a program to judge whether the above three conditions are met by inputting the information of the start point, the goal point, and the intersection, and give it to the lord.

The start point is represented by 1, the goal point is represented by 2, and other intersections are represented by integers of 3 or more. A road is represented by a set of intersection numbers that the roads connect to. The number of intersections shall be 100 or less, and there shall be one or more routes from all intersections to the start point and goal point.



input

Given multiple datasets. Each dataset is given in the following format:


a1 b1
a2 b2
:
:
0 0


The two integers in each row indicate that there is a road connecting intersection ai and intersection bi. When both ai and bi are 0, it indicates the end of inputting intersection information.

The number of datasets does not exceed 50.

output

For each data set, if the samurai's face stands out (if the three conditions are met), OK, otherwise (if the three conditions are not met), output NG on one line.

Example

Input

1 3
3 4
3 5
3 6
4 6
4 7
4 7
5 6
6 7
5 8
5 8
6 8
6 9
7 9
8 9
9 2
0 0
1 3
3 4
3 4
4 2
0 0


Output

OK
NG

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import sys

def is_half_euler_graph(node_list):
	for node in node_list:
		isBool = True
		for (dic_key, dic_value) in node.items():
			if dic_key != 1 and dic_key != 2:
				if dic_value % 2 != 0:
					isBool = False
					break
			elif dic_value % 2 == 0:
				isBool = False
				break
		if isBool:
			print('OK')
		else:
			print('NG')
from collections import defaultdict
data_list = []
for line in sys.stdin:
	data_list.append(list(map(int, line.split())))
node_data_lists = []
tmp_list = []
count_lists = []
tmp_dic = {}
tmp_dic = defaultdict(int)
for i in range(0, len(data_list)):
	if data_list[i][0] == 0 and data_list[i][1] == 0:
		node_data_lists.append(tmp_list[:])
		tmp_list.clear()
	else:
		tmp_list.append(data_list[i])
for node_data_list in node_data_lists:
	tmp_dic.clear()
	for i in range(0, len(node_data_list)):
		tmp_dic[node_data_list[i][0]] += 1
		tmp_dic[node_data_list[i][1]] += 1
	count_lists.append(tmp_dic.copy())
is_half_euler_graph(count_lists)


c = [0] * 100
while 1:
	try:
		(a, b) = map(int, input().split())
	except:
		break
	c[a - 1] += 1
	c[b - 1] += 1
	if a == 0:
		for i in range(2, 100):
			if c[i] & 1:
				print('NG')
				break
		else:
			print('OK' if c[0] & 1 and c[1] & 1 else 'NG')
		c = [0] * 100


import sys
readlines = sys.stdin.readlines
write = sys.stdout.write

def solve():
	L = 100
	G = [[] for i in range(L)]
	for line in readlines():
		(a, b) = map(int, line.split())
		if a != 0 != b:
			G[a - 1].append(b - 1)
			G[b - 1].append(a - 1)
			continue
		ok = 1
		if len(G[0]) % 2 == 0 and len(G[1]) % 2 == 0:
			ok = 0
		else:
			for i in range(2, L):
				if len(G[i]) == 0:
					continue
				if len(G[i]) % 2 == 1:
					ok = 0
		write('OK\n' if ok else 'NG\n')
		G = [[] for i in range(L)]
solve()


import sys
try:
	while True:
		edges = [0] * 101
		while True:
			(a, b) = map(int, input().split())
			if not a:
				break
			edges[a] += 1
			edges[b] += 1
		if edges[1] % 2 == 1 and edges[2] % 2 == 1 and all((n % 2 == 0 for n in edges[3:])):
			print('OK')
		else:
			print('NG')
except EOFError:
	pass


import sys
from sys import stdin
input = stdin.readline

def main(args):
	for line in sys.stdin:
		routes = []
		(a, b) = map(int, line.split())
		if a == 0 and b == 0:
			break
		while a != 0 or b != 0:
			routes.append([a, b])
			(a, b) = map(int, input().split())
		degrees = [0] * 101
		for (a, b) in routes:
			degrees[a] += 1
			degrees[b] += 1
		odds = [x for x in degrees if x % 2 == 1]
		if len(odds) == 2 and degrees[1] % 2 == 1 and (degrees[2] % 2 == 1):
			print('OK')
		else:
			print('NG')
main(sys.argv[1:])


import sys
from collections import defaultdict
data_list = []
for line in sys.stdin:
	data_list.append(list(map(int, line.split())))

def is_half_euler_graph(node_list):
	for node in node_list:
		isBool = True
		for (dic_key, dic_value) in node.items():
			if dic_key != 1 and dic_key != 2:
				if dic_value % 2 != 0:
					isBool = False
					break
			elif dic_value % 2 == 0:
				isBool = False
				break
		if isBool:
			print('OK')
		else:
			print('NG')
node_data_lists = []
tmp_list = []
count_lists = []
tmp_dic = {}
tmp_dic = defaultdict(int)
for i in range(0, len(data_list)):
	if data_list[i][0] == 0 and data_list[i][1] == 0:
		node_data_lists.append(tmp_list[:])
		tmp_list.clear()
	else:
		tmp_list.append(data_list[i])
for node_data_list in node_data_lists:
	tmp_dic.clear()
	for i in range(0, len(node_data_list)):
		tmp_dic[node_data_list[i][0]] += 1
		tmp_dic[node_data_list[i][1]] += 1
	count_lists.append(tmp_dic.copy())
is_half_euler_graph(count_lists)


def solve():
	dic = {}
	while True:
		(a, b) = map(int, input().split())
		if not a:
			break
		if a in dic:
			dic[a] += 1
		else:
			dic[a] = 1
		if b in dic:
			dic[b] += 1
		else:
			dic[b] = 1
	if not dic[1] % 2 or not dic[2] % 2:
		print('NG')
	else:
		for k in dic:
			if not k in (1, 2) and dic[k] % 2:
				print('NG')
				break
		else:
			print('OK')
while True:
	try:
		solve()
	except EOFError:
		break


import sys
v = [0] * 100
for e in sys.stdin:
	(a, b) = map(int, e.split())
	v[a] += 1
	v[b] += 1
	if a == 0:
		print(['NG', 'OK'][(v[1] & 1) * (v[2] & 1) * sum((x & 1 for x in v)) == 2])
		v = [0] * 100


import sys
ab = []
for line in sys.stdin:
	temp = list(map(int, line.split()))
	if temp == [0, 0]:
		v = [0 for i in range(max(ab) + 1)]
		for i in ab:
			v[i] += 1
		odd = 0
		for i in v:
			if i % 2 == 1:
				odd += 1
		if odd == 2 and v[1] % 2 == v[2] % 2 == 1:
			print('OK')
		else:
			print('NG')
		ab = []
	else:
		ab += temp


cntlist = [0] * 102
while 1:
	try:
		(a, b) = map(int, input().split())
	except:
		break
	cntlist[a] += 1
	cntlist[b] += 1
	if a == 0 and b == 0:
		for cnt in cntlist[3:]:
			if cnt % 2 == 1:
				print('NG')
				break
		else:
			print('OK' if cntlist[1] & 1 and cntlist[2] & 1 else 'NG')
		cntlist = [0] * 102


import sys
import os
import math
M = []
for i in range(105):
	M.append([])

def solve(M):
	odd_num = 0
	even_num = 0
	for m in M:
		if len(m) % 2 == 0:
			even_num += 1
		else:
			odd_num += 1
	if odd_num == 2 and len(M[0]) % 2 == 1 and (len(M[1]) % 2 == 1):
		print('OK')
	else:
		print('NG')
for s in sys.stdin:
	(a, b) = map(int, s.split())
	if a == b == 0:
		solve(M)
		M = []
		for i in range(105):
			M.append([])
	else:
		a -= 1
		b -= 1
		M[a].append(b)
		M[b].append(a)


while 1:
	try:
		v = [0] * 101
		(a, b) = map(int, input().split())
		v[a] += 1
		v[b] += 1
		while 1:
			(a, b) = map(int, input().split())
			if a == 0:
				break
			v[a] += 1
			v[b] += 1
		flag = 0
		for num in v[3:]:
			if num % 2 == 1:
				flag = 1
		if v[1] % 2 and v[2] % 2 and (not flag):
			print('OK')
		else:
			print('NG')
	except:
		break


import sys
v = [0] * 101
for e in sys.stdin:
	(a, b) = map(int, e.split())
	v[a] += 1
	v[b] += 1
	if a == 0:
		print(['NG', 'OK'][1 & v[1] and 1 & v[2] and (sum((x & 1 for x in v)) == 2)])
		v = [0] * 101


while True:
	try:
		lst = []
		ju = True
		while True:
			(a, b) = map(int, input().split())
			if a == 0:
				break
			lst.append(a)
			lst.append(b)
		anslst = []
		for i in range(1, max(lst) + 1):
			anslst.append(lst.count(i))
		if anslst[0] % 2 == 0 or anslst[1] % 2 == 0:
			ju = False
		else:
			for i in anslst[2:]:
				if i % 2 != 0:
					ju = False
					break
		if ju:
			print('OK')
		else:
			print('NG')
	except EOFError:
		break


import sys, math, os
PYDEV = os.environ.get('PYDEV')
if PYDEV == 'True':
	sys.stdin = open('sample-input2.txt', 'rt')
a = [0] * 101
while True:
	try:
		(x, y) = [int(_) for _ in input().split()]
	except EOFError:
		break
	if x == y == 0:
		c = sum([a[i] % 2 for i in range(3, 101)])
		print('OK' if c == 0 and a[1] % 2 == 1 and (a[2] % 2 == 1) else 'NG')
		a = [0] * 101
	else:
		a[x] += 1
		a[y] += 1


import sys
v = [0] * 101
for e in sys.stdin:
	(a, b) = map(int, e.split())
	if a == 0:
		print(['NG', 'OK'][1 & v[1] and 1 & v[2] and (sum((x & 1 for x in v[3:])) == 0)])
		v = [0] * 101
	v[a] += 1
	v[b] += 1


def ap(i):
	if len(root) < i:
		for _ in range(i - len(root)):
			root.append(0)
	root[i - 1] = [0, 1][root[i - 1] == 0]
while 1:
	try:
		root = [0, 0]
		while 1:
			(n, m) = map(int, input().split())
			if n == m == 0:
				break
			ap(n)
			ap(m)
		if root.pop(0) + root.pop(0) == 2 and sum(root) == 0:
			print('OK')
		else:
			print('NG')
	except:
		break


import sys
v = [0] * 101
for e in sys.stdin:
	(a, b) = map(int, e.split())
	v[a] += 1
	v[b] += 1
	if a == 0:
		print(['NG', 'OK'][(v[1] & 1) * (v[2] & 1) * sum((x & 1 for x in v)) == 2])
		v = [0] * 101


while True:
	try:
		(a, b) = list(map(int, input().split()))
	except:
		break
	c = [0] * 105
	n = 0
	while True:
		if a != b:
			c[a] += 1
			c[b] += 1
		if a > n:
			n = a
		if b > n:
			n = b
		(a, b) = list(map(int, input().split()))
		if a == 0:
			break
	f = False
	if c[1] & 1 and c[2] & 1:
		i = 3
		while i <= n:
			if c[i] & 1:
				break
			i += 1
		if i > n:
			f = True
	print('OK' if f else 'NG')


while True:
	try:
		d = {}
		while True:
			(a, b) = map(int, input().split())
			if a == 0:
				break
			if a in d:
				d[a] += 1
			else:
				d[a] = 1
			if b in d:
				d[b] += 1
			else:
				d[b] = 1
		if d[1] % 2 == 1 and d[2] % 2 == 1:
			del d[1], d[2]
			for node in d:
				if d[node] % 2 == 1:
					print('NG')
					break
			else:
				print('OK')
		else:
			print('NG')
	except:
		break


import sys
v = [0] * 101
for e in sys.stdin:
	(a, b) = map(int, e.split())
	v[a] += 1
	v[b] += 1
	if a == 0:
		print(['NG', 'OK'][(v[1] & 1) * (v[2] & 1) * sum((x & 1 for x in v)) == 2])
		v = [0] * 100


import sys
f = sys.stdin

def is_odd(num):
	return num % 2 == 1
intersection = [0 for _ in range(101)]
for line in f:
	(a, b) = map(int, line.split())
	if a == b == 0:
		if is_odd(intersection[1]) and is_odd(intersection[2]) and (0 == sum((1 for i in range(3, len(intersection)) if is_odd(intersection[i])))):
			print('OK')
		else:
			print('NG')
		intersection = [0 for _ in range(101)]
	else:
		intersection[a] += 1
		intersection[b] += 1


c = [0] * 100
while 1:
	try:
		(a, b) = map(int, input().split())
	except:
		break
	c[a - 1] += 1
	c[b - 1] += 1
	if a == 0:
		for i in range(2, 100):
			if c[i] & 1:
				print('NG')
				break
		else:
			print('OK' if c[0] & 1 and c[1] & 1 else 'NG')
		c = [0] * 100