Patrol

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.

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

inputFormat

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.

outputFormat

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

样例

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

OK
NG

</p>