
// @snippet<sh19910711/contest:headers.cpp>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <limits>
#include <complex>
#include <functional>
#include <iterator>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

// @snippet<sh19910711/contest:solution/interface.cpp>
namespace solution {
    class ISolution {
    public:
        virtual void init() {};
        virtual bool input() { return false; };
        virtual void output() {};
        virtual int run() = 0;
    };
}

// @snippet<sh19910711/contest:graph/config.cpp>
namespace graph {
    typedef int Weight;
    const Weight DEFAULT_WEIGHT = std::numeric_limits<Weight>().max() / 2;
}

// @snippet<sh19910711/contest:graph/interface.cpp>
namespace graph {
    class IGraph {
    public:
        virtual void init( int n ) = 0;
        virtual void addEdge( int from, int to ) = 0;
        virtual void addVertices() = 0;
        virtual void addEdges() = 0;
        virtual int countVertices() = 0;
        virtual Weight getEdgeCost( int from, int to ) = 0;
        virtual void setEdgeCost( int from, int to, Weight weight ) = 0;
        virtual Weight getVertexCost( int v ) = 0;
        virtual void setVertexCost( int v, Weight weight ) = 0;
    };
}

// @snippet<sh19910711/contest:graph/adjacent_list.cpp>
namespace graph {
    class AdjacentListGraph: public IGraph {
    public:
        typedef std::vector<int> VI;
        typedef std::vector<VI> Edges;
        typedef std::vector<Weight> Weights;
        typedef std::vector<Weights> EdgeWeights;
        typedef std::vector<VI> Matrix;
        typedef VI::iterator VertexIterator;
        
        Edges edges;
        EdgeWeights edge_weights;
        Weights vertex_weights;
        Matrix edge_exists;
        int num;
        
        void init( int n ) {
            num = n;
            edges.resize(num);
            vertex_weights.resize(num);
            edge_weights.resize(num);
            edge_exists.resize(num);
            std::fill( edges.begin(), edges.end(), VI() );
            std::fill( edge_weights.begin(), edge_weights.end(), Weights( num, 0 ) );
            std::fill( edge_exists.begin(), edge_exists.end(), VI( num, false ) );
            addVertices();
            addEdges();
        }
        void addEdge( int from, int to ) {
            if ( edge_exists[from][to] )
                return;
            edge_exists[from][to] = true;
            edges[from].push_back(to);
        }
        void addEdge( int from, int to, Weight weight ) {
            addEdge( from, to );
            setEdgeCost( from, to, weight );
        }
        int countVertices() {
            return num;
        }
        Weight getVertexCost( int from ) {
            return vertex_weights[from];
        }
        void setVertexCost( int from, Weight weight ) {
            vertex_weights[from] = weight;
        }
        Weight getEdgeCost( int from, int to ) {
            return edge_weights[from][to];
        }
        void setEdgeCost( int from, int to, Weight weight ) {
            edge_weights[from][to] = weight;
        }
        VertexIterator begin( int from ) {
            return edges[from].begin();
        }
        VertexIterator end( int from ) {
            return edges[from].end();
        }
    };
}


// @snippet<sh19910711/contest:solution/solution.cpp>
namespace solution {
    using namespace std;
    
    const int SIZE = 10001;
    int n;
    string A[SIZE];
    bool U[26];
    int vertices;

    class Graph: public graph::AdjacentListGraph {
    public:
        int findNode( char c ) {
            return c - 'a';
        }

        void init( int num ) {
            vertices = 0;
            graph::AdjacentListGraph::init(num);
        }

        graph::Weight& edge( int from, int to ) {
            return edge_weights[from][to];
        }

        void addVertices() {
            for ( int i = 0; i < n; ++ i ) {
                int a = findNode(*A[i].begin());
                int b = findNode(*A[i].rbegin());
                if ( a == b )
                    continue;
                if ( ! U[a] )
                    vertices ++;
                if ( ! U[b] )
                    vertices ++;
                U[a] = U[b] = true;
            }
        }

        void addEdges() {
            for ( int i = 0; i < n; ++ i ) {
                int a = findNode(*A[i].begin());
                int b = findNode(*A[i].rbegin());
                if ( a == b )
                    continue;
                addEdge( a, b, 0 );
            }
            for ( int i = 0; i < n; ++ i ) {
                int a = findNode(*A[i].begin());
                int b = findNode(*A[i].rbegin());
                if ( a == b )
                    continue;
                edge(a,b) ++;
            }
        }
    };

    int GetConnectedVertices( graph::AdjacentListGraph& graph, int start_vertex ) {
        int n = graph.num;
        bool used[n];
        fill( used, used+n, false );
        queue <int> Q;
        Q.push(start_vertex);
        used[start_vertex] = true;
        int res = 1;
        while ( ! Q.empty() ) {
            int current_vertex = Q.front();
            Q.pop();
            for ( vector<int>::iterator it_i = graph.begin(current_vertex);
               it_i != graph.end(current_vertex); ++ it_i ) {
                int& next_vertex = *it_i;
                if ( used[next_vertex] )
                    continue;
                used[next_vertex] = true;
                res ++;
                Q.push(next_vertex);
            }
        }
        return res;
    }
    
    class Solution: public ISolution {
    public:
        Graph G;
        void init() {
            fill( U, U+26, false );
        }
        bool input() {
            if ( ! ( cin >> n && n ) )
                return false;
            for ( int i = 0; i < n; ++ i )
                cin >> A[i];
            return true;
        }
        bool solve() {
            G.init(26);

            for ( int i = 0; i < 26; ++ i ) {
                if ( U[i] ) {
                    int ret = GetConnectedVertices( G, i );
                    if ( ret != vertices )
                        return false;
                    break;
                }
            }

            for ( int i = 0; i < 26; ++ i ) {
                if ( ! U[i] )
                    continue;
                int cnt_in = 0;
                int cnt_out = 0;
                for ( int j = 0; j < 26; ++ j ) {
                    if ( ! U[j] )
                        continue;
                    cnt_in += G.edge( j, i );
                    cnt_out += G.edge( i, j );
                }
                if ( cnt_in != cnt_out )
                    return false;
            }

            return true;
        }
        void output( bool result ) {
            cout << ( result ? "OK" : "NG" ) << endl;
        }
        int run() {
            while ( init(), input() ) {
                output( solve() );
            }
            return 0;
        }
    };
}


// @snippet<sh19910711/contest:main.cpp>

int main() {
    return solution::Solution().run();
}
### Prompt

Please formulate a CPP solution to the following problem:

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

// @snippet<sh19910711/contest:headers.cpp>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <limits>
#include <complex>
#include <functional>
#include <iterator>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

// @snippet<sh19910711/contest:solution/interface.cpp>
namespace solution {
    class ISolution {
    public:
        virtual void init() {};
        virtual bool input() { return false; };
        virtual void output() {};
        virtual int run() = 0;
    };
}

// @snippet<sh19910711/contest:graph/config.cpp>
namespace graph {
    typedef int Weight;
    const Weight DEFAULT_WEIGHT = std::numeric_limits<Weight>().max() / 2;
}

// @snippet<sh19910711/contest:graph/interface.cpp>
namespace graph {
    class IGraph {
    public:
        virtual void init( int n ) = 0;
        virtual void addEdge( int from, int to ) = 0;
        virtual void addVertices() = 0;
        virtual void addEdges() = 0;
        virtual int countVertices() = 0;
        virtual Weight getEdgeCost( int from, int to ) = 0;
        virtual void setEdgeCost( int from, int to, Weight weight ) = 0;
        virtual Weight getVertexCost( int v ) = 0;
        virtual void setVertexCost( int v, Weight weight ) = 0;
    };
}

// @snippet<sh19910711/contest:graph/adjacent_list.cpp>
namespace graph {
    class AdjacentListGraph: public IGraph {
    public:
        typedef std::vector<int> VI;
        typedef std::vector<VI> Edges;
        typedef std::vector<Weight> Weights;
        typedef std::vector<Weights> EdgeWeights;
        typedef std::vector<VI> Matrix;
        typedef VI::iterator VertexIterator;
        
        Edges edges;
        EdgeWeights edge_weights;
        Weights vertex_weights;
        Matrix edge_exists;
        int num;
        
        void init( int n ) {
            num = n;
            edges.resize(num);
            vertex_weights.resize(num);
            edge_weights.resize(num);
            edge_exists.resize(num);
            std::fill( edges.begin(), edges.end(), VI() );
            std::fill( edge_weights.begin(), edge_weights.end(), Weights( num, 0 ) );
            std::fill( edge_exists.begin(), edge_exists.end(), VI( num, false ) );
            addVertices();
            addEdges();
        }
        void addEdge( int from, int to ) {
            if ( edge_exists[from][to] )
                return;
            edge_exists[from][to] = true;
            edges[from].push_back(to);
        }
        void addEdge( int from, int to, Weight weight ) {
            addEdge( from, to );
            setEdgeCost( from, to, weight );
        }
        int countVertices() {
            return num;
        }
        Weight getVertexCost( int from ) {
            return vertex_weights[from];
        }
        void setVertexCost( int from, Weight weight ) {
            vertex_weights[from] = weight;
        }
        Weight getEdgeCost( int from, int to ) {
            return edge_weights[from][to];
        }
        void setEdgeCost( int from, int to, Weight weight ) {
            edge_weights[from][to] = weight;
        }
        VertexIterator begin( int from ) {
            return edges[from].begin();
        }
        VertexIterator end( int from ) {
            return edges[from].end();
        }
    };
}


// @snippet<sh19910711/contest:solution/solution.cpp>
namespace solution {
    using namespace std;
    
    const int SIZE = 10001;
    int n;
    string A[SIZE];
    bool U[26];
    int vertices;

    class Graph: public graph::AdjacentListGraph {
    public:
        int findNode( char c ) {
            return c - 'a';
        }

        void init( int num ) {
            vertices = 0;
            graph::AdjacentListGraph::init(num);
        }

        graph::Weight& edge( int from, int to ) {
            return edge_weights[from][to];
        }

        void addVertices() {
            for ( int i = 0; i < n; ++ i ) {
                int a = findNode(*A[i].begin());
                int b = findNode(*A[i].rbegin());
                if ( a == b )
                    continue;
                if ( ! U[a] )
                    vertices ++;
                if ( ! U[b] )
                    vertices ++;
                U[a] = U[b] = true;
            }
        }

        void addEdges() {
            for ( int i = 0; i < n; ++ i ) {
                int a = findNode(*A[i].begin());
                int b = findNode(*A[i].rbegin());
                if ( a == b )
                    continue;
                addEdge( a, b, 0 );
            }
            for ( int i = 0; i < n; ++ i ) {
                int a = findNode(*A[i].begin());
                int b = findNode(*A[i].rbegin());
                if ( a == b )
                    continue;
                edge(a,b) ++;
            }
        }
    };

    int GetConnectedVertices( graph::AdjacentListGraph& graph, int start_vertex ) {
        int n = graph.num;
        bool used[n];
        fill( used, used+n, false );
        queue <int> Q;
        Q.push(start_vertex);
        used[start_vertex] = true;
        int res = 1;
        while ( ! Q.empty() ) {
            int current_vertex = Q.front();
            Q.pop();
            for ( vector<int>::iterator it_i = graph.begin(current_vertex);
               it_i != graph.end(current_vertex); ++ it_i ) {
                int& next_vertex = *it_i;
                if ( used[next_vertex] )
                    continue;
                used[next_vertex] = true;
                res ++;
                Q.push(next_vertex);
            }
        }
        return res;
    }
    
    class Solution: public ISolution {
    public:
        Graph G;
        void init() {
            fill( U, U+26, false );
        }
        bool input() {
            if ( ! ( cin >> n && n ) )
                return false;
            for ( int i = 0; i < n; ++ i )
                cin >> A[i];
            return true;
        }
        bool solve() {
            G.init(26);

            for ( int i = 0; i < 26; ++ i ) {
                if ( U[i] ) {
                    int ret = GetConnectedVertices( G, i );
                    if ( ret != vertices )
                        return false;
                    break;
                }
            }

            for ( int i = 0; i < 26; ++ i ) {
                if ( ! U[i] )
                    continue;
                int cnt_in = 0;
                int cnt_out = 0;
                for ( int j = 0; j < 26; ++ j ) {
                    if ( ! U[j] )
                        continue;
                    cnt_in += G.edge( j, i );
                    cnt_out += G.edge( i, j );
                }
                if ( cnt_in != cnt_out )
                    return false;
            }

            return true;
        }
        void output( bool result ) {
            cout << ( result ? "OK" : "NG" ) << endl;
        }
        int run() {
            while ( init(), input() ) {
                output( solve() );
            }
            return 0;
        }
    };
}


// @snippet<sh19910711/contest:main.cpp>

int main() {
    return solution::Solution().run();
}
```