//#include "pch.h"
//#include "stdafx.h"
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <math.h>
#include <string>
#include <cstring>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>

using namespace std;

typedef long long int ll;
#define BIG_NUM 2000000000
using namespace std;

struct Info{

	Info(){
		left = right = 'X';
		index = 0;
	}

	Info(char arg_left,char arg_right,int arg_index){
		left = arg_left;
		right = arg_right;
		index = arg_index;
	}
	char left,right;
	int index;
};

bool check[10000];
vector<Info> V[26];

void dfs(char left){
	for(int i = 0; i < V[left - 'a'].size(); i++){
		if(check[V[left - 'a'][i].index] == false){
			check[V[left - 'a'][i].index] = true;
			dfs(V[left - 'a'][i].right);
		}
	}
}

int execOne(){

	int N,num_left[26],num_right[26];

	bool FLG;

	char last,final_start;
	string buf;

	while(true){
		cin >> N;
		if(N == 0)break;

		FLG = true;

		for(int i = 0; i < 26; i++){
			V[i].clear();
			num_left[i] = 0;
			num_right[i] = 0;
		}
		for(int i = 0; i < N; i++)check[i] = false;

		for(int i = 0; i < N; i++){
			cin >> buf;
			num_left[buf[0] - 'a']++;
			for(int k = 0; buf[k] != '\0'; k++)last = buf[k];
			num_right[last - 'a']++;
			V[buf[0]-'a'].push_back(Info(buf[0],last,i));
			final_start = buf[0];
		}

		for(int i = 0; i < 26; i++){
			if(num_left[i] != num_right[i]){
				printf("NG\n");
				FLG = false;
				break;
			}
		}

		if(!FLG)continue;

		check[V[final_start - 'a'][0].index] = true;
		dfs(V[final_start - 'a'][0].right);

		for(int i = 0; i < N; i++){
			if(check[i] == false){
				printf("NG\n");
				FLG = false;
				break;
			}
		}

		if(!FLG)continue;

		printf("OK\n");

	}

	return 0;
}

#if 0
/*-----------------------------------------------------------------------------
　ライブラリ
 -------------------------------------------------------------------------------*/
#if 0
// 3次元
vector<vector<vector<SDWORD>>> XXX(AAA, vector<vector<SDWORD>>(BBBB, vector<SDWORD>(CCC, -1)));
#endif

#if 0
// 降順ソート
sort(getValue.rbegin(), getValue.rend());
#endif

#if 0
// 2分探索
auto position = lower_bound(getValue.begin(), getValue.end(), 0);	// 0以上の要素位置を探す
int idx_lower = distance(getValue.begin(), position);				// 0以上の要素インデックス
int eraseNum = MIN(idx_lower, delCnt);								// 要素位置が個数になる
if (0 < eraseNum) {
	getValue.erase(getValue.begin(), getValue.begin() + eraseNum);
}
#endif

/*-----------------------------------------------------------------------------
　定義
 -------------------------------------------------------------------------------*/
#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))

#define INF				2e9
#define MOD				(1000 * 1000 * 1000 + 7)
#define MIN(a, b)		((a) < (b) ? a : b)
#define MAX(a, b)		((a) > (b) ? a : b)
#define CeilN(x, n)		(((((DWORD)(x))+((n)-1))/n)*n)	/* Nの倍数に切り上げ */
#define FloorN(x, n)	((x)-(x)%(n))					/* Nの倍数に切り下げ */
#define IsOdd(x)		(((x)&0x01UL) == 0x01UL)			
#define IsEven(x)		(!IsOdd((x)))						

#define ArrayLength(x)	( sizeof( x ) / sizeof( x[ 0 ] ) )
#define	ArrayEnd(a)		(&(a)[ArrayLength(a)])			
#define	ArrayLast(a)	(&(a)[ArrayLength(a) - 1])		
#define MAX_BYTE		(255)
#define MIN_BYTE		(0)
#define MAX_WORD		(65535)
#define MIN_WORD		(0)
#define MAX_SWORD		(32767)
#define MIN_SWORD		(-32768)
#define MAX_DWORD		(0xFFFFFFFF)
#define MIN_DWORD		(0)
#define	MAX_SDWORD		((SDWORD)0x7FFFFFFF)
#define	MIN_SDWORD		((SDWORD)0x80000000)
#define	MAX_QWORD		((QWORD)0xFFFFFFFFFFFFFFFF)
#define	MIN_QWORD		((QWORD)0x0000000000000000)
#define	MAX_SQWORD		((SQWORD)0x7FFFFFFFFFFFFFFF)
#define	MIN_SQWORD		((SQWORD)0x8000000000000000)

#define	BitSetV(Val,Bit)		((Val) |= (Bit))			
#define	BitClrV(Val,Bit)		((Val) &= (~(Bit)))			
#define	BitTstV(Val,Bit)		((Val) & (Bit))				
#define	BitInvV(Val,Bit)		((Val) ^= (Bit))			
#define	BitTstVVal(Val, Bit)	(BitTstV((Val), (Bit)) == (Bit))	

typedef short					SWORD;
typedef long					SDWORD;
typedef long long				SQWORD;
typedef unsigned short			WORD;
typedef unsigned long			DWORD;
typedef unsigned long long int	QWORD;
typedef pair<int, int> P;

/*-----------------------------------------------------------------------------
　パラメータ定義
 -------------------------------------------------------------------------------*/
#define N_MAX	(10)
#define K_MAX	(10)
#define M_MAX	(1000)
#define H_MAX	(1000)
#define W_MAX	(1000)
/*-----------------------------------------------------------------------------
　処理
 -------------------------------------------------------------------------------*/
///
struct wordInfo {
	wordInfo() {
		index = 0;
		to = 'Z';
	}

	wordInfo(int a, char b) {
		index = a;
		to = b;
	}
	int	index;
	int to;
};
vector<bool>		execResult;
vector<wordInfo>	wordList[26];

/// dfs
void dfs(int topWord)
{
	//	vector<wordInfo> &wordOne = wordList[topWord];

	for (size_t i = 0; i < wordList[topWord].size(); i++) {
		if (!execResult[wordList[topWord][i].index]) {
			execResult[wordList[topWord][i].index] = true;
			dfs(wordList[topWord][i].to);
		}
	}
}

/// 1塊判定
bool execOne(int n)
{
	int lastWord;
	int topNum[26];
	int endNum[26];

	// 初期化
	REP(i, 26) {
		wordList[i].clear();
		topNum[i] = 0;
		endNum[i] = 0;
	}
	execResult.resize(n, false);

	// 入力
	REP(i, n) {
		string strOne;
//		const char *pStrOne = strOne.c_str();
		cin >> strOne;
		int topWord = *strOne.begin() - 'a';
		int endWord = *(strOne.end() - 1) - 'a';
		topNum[topWord]++;
		endNum[endWord]++;
		wordList[topWord].push_back(wordInfo(i, endWord));
		lastWord = endWord;
	}

	// 先頭と末尾の数は一緒のはず
	REP(i, n) {
		if (topNum[i] != endNum[i]) {
			return false;
		}
	}

	// dfs
	execResult[n - 1] = true;
	dfs(lastWord);

	// 結果チェック
	REP(i, n) {
		if (!execResult[i]) {
			return false;
		}
	}
	return true;
}
#endif

/// メイン
int main()
{
	execOne();
	/*
	while (1) {
		int n;
		cin >> n;
		if (n == 0) {
			break;
		}
		if (execOne(n)) {
			cout << "OK" << endl;
		} else {
			cout << "NG" << endl;
		}
	}

	cout << endl;*/
	return 0;
}




### Prompt

Please provide a cpp coded solution to the problem described below:

Relative B man came to A child's house. He is 3 years old and loves singing. He is singing the song "Kobutanuki Tsuneko" (written and composed by Naozumi Yamamoto), which he learned from kindergarten. In this song, the four words "kobuta," "raccoon dog," "fox," and "cat" are arranged in order, and the last and first sounds are the same. Mr. B was asked by Mr. A to tell him if he could make a similar shiritori from the words that Mr. B said.

So, in order to help Ako, from the given words, use all the words to make a shiritori in order, and then the first letter of the first word and the last letter of the last word are the same. Let's write a program that determines whether or not it can be done.

Create a program that takes n words as input, determines whether or not a shiritori can be created from those word pairs, and outputs OK if possible and NG if not.



Input

A sequence of multiple datasets is given as input. The end of the input is indicated by a single line of zeros. Each dataset is given in the following format:


n
word1
word2
::
wordn


The number of words n (2 ≤ n ≤ 10000) is given on the first line. The next n lines are given n words wordi (a string of up to 32 single-byte lowercase letters).

The number of datasets does not exceed 50.

Output

The judgment result is output to one line for each input data set.

Example

Input

5
apple
yellow
georgia
king
email
7
apple
yellow
georgia
king
email
wink
lucky
0


Output

NG
OK

### Response

```cpp
//#include "pch.h"
//#include "stdafx.h"
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <math.h>
#include <string>
#include <cstring>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>

using namespace std;

typedef long long int ll;
#define BIG_NUM 2000000000
using namespace std;

struct Info{

	Info(){
		left = right = 'X';
		index = 0;
	}

	Info(char arg_left,char arg_right,int arg_index){
		left = arg_left;
		right = arg_right;
		index = arg_index;
	}
	char left,right;
	int index;
};

bool check[10000];
vector<Info> V[26];

void dfs(char left){
	for(int i = 0; i < V[left - 'a'].size(); i++){
		if(check[V[left - 'a'][i].index] == false){
			check[V[left - 'a'][i].index] = true;
			dfs(V[left - 'a'][i].right);
		}
	}
}

int execOne(){

	int N,num_left[26],num_right[26];

	bool FLG;

	char last,final_start;
	string buf;

	while(true){
		cin >> N;
		if(N == 0)break;

		FLG = true;

		for(int i = 0; i < 26; i++){
			V[i].clear();
			num_left[i] = 0;
			num_right[i] = 0;
		}
		for(int i = 0; i < N; i++)check[i] = false;

		for(int i = 0; i < N; i++){
			cin >> buf;
			num_left[buf[0] - 'a']++;
			for(int k = 0; buf[k] != '\0'; k++)last = buf[k];
			num_right[last - 'a']++;
			V[buf[0]-'a'].push_back(Info(buf[0],last,i));
			final_start = buf[0];
		}

		for(int i = 0; i < 26; i++){
			if(num_left[i] != num_right[i]){
				printf("NG\n");
				FLG = false;
				break;
			}
		}

		if(!FLG)continue;

		check[V[final_start - 'a'][0].index] = true;
		dfs(V[final_start - 'a'][0].right);

		for(int i = 0; i < N; i++){
			if(check[i] == false){
				printf("NG\n");
				FLG = false;
				break;
			}
		}

		if(!FLG)continue;

		printf("OK\n");

	}

	return 0;
}

#if 0
/*-----------------------------------------------------------------------------
　ライブラリ
 -------------------------------------------------------------------------------*/
#if 0
// 3次元
vector<vector<vector<SDWORD>>> XXX(AAA, vector<vector<SDWORD>>(BBBB, vector<SDWORD>(CCC, -1)));
#endif

#if 0
// 降順ソート
sort(getValue.rbegin(), getValue.rend());
#endif

#if 0
// 2分探索
auto position = lower_bound(getValue.begin(), getValue.end(), 0);	// 0以上の要素位置を探す
int idx_lower = distance(getValue.begin(), position);				// 0以上の要素インデックス
int eraseNum = MIN(idx_lower, delCnt);								// 要素位置が個数になる
if (0 < eraseNum) {
	getValue.erase(getValue.begin(), getValue.begin() + eraseNum);
}
#endif

/*-----------------------------------------------------------------------------
　定義
 -------------------------------------------------------------------------------*/
#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))

#define INF				2e9
#define MOD				(1000 * 1000 * 1000 + 7)
#define MIN(a, b)		((a) < (b) ? a : b)
#define MAX(a, b)		((a) > (b) ? a : b)
#define CeilN(x, n)		(((((DWORD)(x))+((n)-1))/n)*n)	/* Nの倍数に切り上げ */
#define FloorN(x, n)	((x)-(x)%(n))					/* Nの倍数に切り下げ */
#define IsOdd(x)		(((x)&0x01UL) == 0x01UL)			
#define IsEven(x)		(!IsOdd((x)))						

#define ArrayLength(x)	( sizeof( x ) / sizeof( x[ 0 ] ) )
#define	ArrayEnd(a)		(&(a)[ArrayLength(a)])			
#define	ArrayLast(a)	(&(a)[ArrayLength(a) - 1])		
#define MAX_BYTE		(255)
#define MIN_BYTE		(0)
#define MAX_WORD		(65535)
#define MIN_WORD		(0)
#define MAX_SWORD		(32767)
#define MIN_SWORD		(-32768)
#define MAX_DWORD		(0xFFFFFFFF)
#define MIN_DWORD		(0)
#define	MAX_SDWORD		((SDWORD)0x7FFFFFFF)
#define	MIN_SDWORD		((SDWORD)0x80000000)
#define	MAX_QWORD		((QWORD)0xFFFFFFFFFFFFFFFF)
#define	MIN_QWORD		((QWORD)0x0000000000000000)
#define	MAX_SQWORD		((SQWORD)0x7FFFFFFFFFFFFFFF)
#define	MIN_SQWORD		((SQWORD)0x8000000000000000)

#define	BitSetV(Val,Bit)		((Val) |= (Bit))			
#define	BitClrV(Val,Bit)		((Val) &= (~(Bit)))			
#define	BitTstV(Val,Bit)		((Val) & (Bit))				
#define	BitInvV(Val,Bit)		((Val) ^= (Bit))			
#define	BitTstVVal(Val, Bit)	(BitTstV((Val), (Bit)) == (Bit))	

typedef short					SWORD;
typedef long					SDWORD;
typedef long long				SQWORD;
typedef unsigned short			WORD;
typedef unsigned long			DWORD;
typedef unsigned long long int	QWORD;
typedef pair<int, int> P;

/*-----------------------------------------------------------------------------
　パラメータ定義
 -------------------------------------------------------------------------------*/
#define N_MAX	(10)
#define K_MAX	(10)
#define M_MAX	(1000)
#define H_MAX	(1000)
#define W_MAX	(1000)
/*-----------------------------------------------------------------------------
　処理
 -------------------------------------------------------------------------------*/
///
struct wordInfo {
	wordInfo() {
		index = 0;
		to = 'Z';
	}

	wordInfo(int a, char b) {
		index = a;
		to = b;
	}
	int	index;
	int to;
};
vector<bool>		execResult;
vector<wordInfo>	wordList[26];

/// dfs
void dfs(int topWord)
{
	//	vector<wordInfo> &wordOne = wordList[topWord];

	for (size_t i = 0; i < wordList[topWord].size(); i++) {
		if (!execResult[wordList[topWord][i].index]) {
			execResult[wordList[topWord][i].index] = true;
			dfs(wordList[topWord][i].to);
		}
	}
}

/// 1塊判定
bool execOne(int n)
{
	int lastWord;
	int topNum[26];
	int endNum[26];

	// 初期化
	REP(i, 26) {
		wordList[i].clear();
		topNum[i] = 0;
		endNum[i] = 0;
	}
	execResult.resize(n, false);

	// 入力
	REP(i, n) {
		string strOne;
//		const char *pStrOne = strOne.c_str();
		cin >> strOne;
		int topWord = *strOne.begin() - 'a';
		int endWord = *(strOne.end() - 1) - 'a';
		topNum[topWord]++;
		endNum[endWord]++;
		wordList[topWord].push_back(wordInfo(i, endWord));
		lastWord = endWord;
	}

	// 先頭と末尾の数は一緒のはず
	REP(i, n) {
		if (topNum[i] != endNum[i]) {
			return false;
		}
	}

	// dfs
	execResult[n - 1] = true;
	dfs(lastWord);

	// 結果チェック
	REP(i, n) {
		if (!execResult[i]) {
			return false;
		}
	}
	return true;
}
#endif

/// メイン
int main()
{
	execOne();
	/*
	while (1) {
		int n;
		cin >> n;
		if (n == 0) {
			break;
		}
		if (execOne(n)) {
			cout << "OK" << endl;
		} else {
			cout << "NG" << endl;
		}
	}

	cout << endl;*/
	return 0;
}




```