Problem: 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

Solution (in JAVA):

Solution:

import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		Scanner stdIn = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		CON:while(sc.hasNext()) {
			int[] list = new int[1000];
			while(true) {
				int a = sc.nextInt();
				int b = sc.nextInt();
				if(a == 0 && b == 0) break;
				list[a]++;
				list[b]++;
			}
			if(list[1] % 2 != 1 || list[2] % 2 != 1) {
				out.println("NG");
				continue CON;
			}
			for(int i = 3; i < list.length; i++) {
				if(list[i] % 2 == 1) {
					out.println("NG");
					continue CON;
				}
			}
			out.println("OK");
		}
		out.flush();
	}
}
class LL {
	int size;
	Node now;
	LL(int n) {
		now = new Node(null,null,1);
		Node tmp = new Node(null,null,2);
		now.next = tmp;
		now.prev = tmp;
		tmp.next = now;
		tmp.prev = now;
		size = n;
		now = tmp;
		for(int i = 2; i < n; i++) {
			add(i+1);
		}
	}
	
	void add(int a) {
		Node tmp = new Node(null,null,a);
		tmp.next = now.next;
		tmp.prev = now;
		now.next.prev = tmp;
		now.next = tmp;
		now = tmp;
	}
	
	void remove() {
		now.prev.next = now.next;
		now.next.prev = now.prev;
		now = now.next;
		size--;
	}
}

class Node {
	Node next;
	Node prev;
	int id;
	Node(Node a, Node b, int c) {
		next = a;
		prev = b;
		id = c;
	}
}
//------------------------------//
//-----------//
class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}
    public boolean hasNext() { skipUnprintable(); return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    
    public int nextInt() {
    	return (int)nextLong();
    }
    

}