PROG0218 - Word chain

no tags 

A set of words is a word chain if all the words from the set are of the same length and two consecutive words from the set each differ one letter from each other. The order of the letters is important, in the sense that at any position of the two words every single letter has to be the same, except at a single position where there is a different letter. If all the consecutive words from a sequence differ one letter from each other each time, regardless of the order in which the letters appear in any two consecutive words, it is called a semi-word chain. Note that a word chain is also a semi-word chain, but not vice versa.

Input

The first line of the input contains an integer $n \in \mathbb{N}$. This is followed by $n$ words that consist only of uppercase letters and are each on a separate line.

Output

If the set of words is a word chain, you print word chain to the output. If the sequence is not a word chain, but a semi-word chain, you print the term semi-word chain to the output. Otherwise, you print no word chain to the output.

Example

Input:

20
KOLDER
HOLDER
HELDER
HERDER
VERDER
VERVER
VERSER
VELSER
VELTER
VESTER
TESTER
OESTER
MESTER
HESTER
LESTER
PESTER
BESTER
KESTER
KENTER
KETTER

Output:

word chain

Example

Input:

18
GEOGRAAF
ROGGEAAR
OVERGAAG
OVERGAAN
AANVOEGT
TOVENAAR
VETERAAN
RELEVANT
AFVRETEN
AFVOEREN
AFROEPEN
AFPOEIER
AFROEIDE
AFVOERDE
VERTOEFD
DRIEVOET
VERMOEID
OVERHEMD

Output:

semi-word chain

Een reeks woorden vormt een woordketting indien alle woorden uit de reeks even lang zijn en twee opeenvolgende woorden uit de reeks telkens één letter van elkaar verschillen. De volgorde van de letters is daarbij belangrijk, in die zin dat op elke positie van de twee woorden telkens eenzelfde letter moet voorkomen, behalve op één enkele positie waar er een verschillende letter moet staan. Indien alle opeenvolgende woorden uit een woordenreeks telkens één letter van elkaar verschillen, los van de volgorde waarin de letters in elke twee opeenvolgende woorden voorkomen, dan noemt men dit een semi-woordketting. Merk op dat een woordketting dus ook een semi-woordketting is, maar niet omgekeerd.

Invoer

De eerste regel van de invoer bevat een getal $n \in \mathbb{N}$. Daarna volgen $n$ woorden die enkel bestaan uit hoofdletters en die elk op een afzonderlijke regel staan.

Uitvoer

Indien de reeks woorden een woordketting vormt, schrijf je de term woordketting naar de uitvoer. Indien de woordenreeks geen woordketting is, maar wel een semi-woordketting, schrijf je de term semi-woordketting naar de uitvoer. Anders schrijf je de term geen woordketting naar de uitvoer.

Voorbeeld

Invoer:

20
KOLDER
HOLDER
HELDER
HERDER
VERDER
VERVER
VERSER
VELSER
VELTER
VESTER
TESTER
OESTER
MESTER
HESTER
LESTER
PESTER
BESTER
KESTER
KENTER
KETTER

Uitvoer:

woordketting

Voorbeeld

Invoer:

18
GEOGRAAF
ROGGEAAR
OVERGAAG
OVERGAAN
AANVOEGT
TOVENAAR
VETERAAN
RELEVANT
AFVRETEN
AFVOEREN
AFROEPEN
AFPOEIER
AFROEIDE
AFVOERDE
VERTOEFD
DRIEVOET
VERMOEID
OVERHEMD

Uitvoer:

semi-woordketting


Added by:Peter Dawyndt
Date:2012-02-10
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:PY_NBC
Resource:None